A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs
-
- NAKAYAMA Shin-ichi
- Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima
-
- MASUYAMA Shigeru
- Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
この論文をさがす
説明
The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
収録刊行物
-
- IEICE transactions on information and systems
-
IEICE transactions on information and systems 89 (8), 2357-2363, 2006-08-01
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570009752661185152
-
- NII論文ID
- 110007538522
-
- NII書誌ID
- AA10826272
-
- ISSN
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles