https://scholars.lib.ntu.edu.tw/handle/123456789/329032
標題: | Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs | 作者: | Lin, C.-C. GERARD JENNHWA CHANG Chen, Gen-Huey |
關鍵字: | Algorithm; Circular-arc graph; Directed path graph; Interval graph; Locally connected spanning tree; Proper circular-arc graph; Strongly chordal graph | 公開日期: | 2007 | 卷: | 307 | 期: | 2 | 起(迄)頁: | 208-215 | 來源出版物: | Discrete Mathematics | 摘要: | A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v ∈ V (G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively. © 2006 Elsevier B.V. All rights reserved. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-33845199907&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/329032 |
DOI: | 10.1016/j.disc.2006.06.026 | SDG/關鍵字: | Algorithms; Set theory; Circular arc graph; Directed path graph; Interval graph; Locally connected spanning tree; Proper circular arc graph; Strongly chordal graph; Trees (mathematics) |
顯示於: | 數學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。