A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set <i>V<sub>NT</sub></i> on Interval Graphs
-
- NAKAYAMA Shin-ichi
- Department of Science and Technology, Tokushima University
-
- MASUYAMA Shigeru
- Department of Computer Science and Engineering, Toyohashi University of Technology
抄録
<p>Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph then finding a spanning tree with a non-terminal set VNT of G is linearly-solvable when each edge has the weight of one.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E101.D (9), 2235-2246, 2018-09-01
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390564238016798720
-
- NII論文ID
- 130007479655
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可