English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26999/38800
Visitors : 2398530      Online Users : 60
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40455

Title: A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs
Authors: Ching-Chi Lin
Gen-Huey Chen
Gerard J. Chang
Contributors: 國立臺灣海洋大學:資訊工程學系
Keywords: Spanning tree
Circular-arc graph
Interval graph
Locally connected spanning tree
Date: 2013
Issue Date: 2017-01-19T02:57:38Z
Publisher: Algorithmica
Abstract: Abstract: Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.
Relation: 66(2)
URI: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40455
Appears in Collections:[資訊工程學系] 期刊論文

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback