文献

J-GLOBAL ID：201902243691929703   整理番号：19A1174930

直列-並列グラフ上の非終端集合V_NTによる最小スパンニング木発見のための線形時間アルゴリズム

A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set V_NT on Series-Parallel Graphs

著者 (2件)： NAKAYAMA Shin-ichi (Department of Science and Technology, Tokushima University) ,  MASUYAMA Shigeru (Department of Management, School of Management, Tokyo University of Science)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E102.D  号： 4  ページ： 826-835(J-STAGE)  発行年： 2019年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： VとEがGの頂点と辺の集合であり,非終端集合と呼ばれる頂点の部分集合をV_NTとするようなグラフG=(V,E)が与えられた時,MSTNTと表現される,非終端集合V_NTによる最小スパンニング木は,Gの,接続された非環状のスパンニング部分グラフであり,Vの最小重みの全ての頂点を含み,非終端集合の各頂点は葉ではない。一般的なグラフでは,GのMSTNTを見つける問題はNP困難である。Gが直列-並列グラフであるならば,GのMSTNTを見つけることは,頂点の数に関して線形的に解けることを示した。(翻訳著者抄録)

シソーラス用語： *スパンニング木 ,  *アルゴリズム ,  NP困難 ,  *グラフ ,  部分集合 ,  *線形時間アルゴリズム

著者キーワード (3件)： スパンニング木 ,  直並列グラフ ,  アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (10件)：

• [1] S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese, “An algebraic theory of graph reduction,” J. Assoc. Comput. Mach., vol.40, no.5, pp.1134-1164, 1993. 10.1145/174147.169807
• [2] S. Arnborg, J. Lagergren, and D. Seese, “Easy problems for tree-decomposable graphs,” J. Algorithms, vol.12, no.2, pp.308-340, 1991. 10.1016/0196-6774(91)90006-k
• [3] A. Brandstadt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999. 10.1137/1.9780898719796
• [4] R. Diestel, Graph Theory, Springer-Verlag, New York, 2000.
• [5] S. Nakayama and S. Masuyama, “A linear-time algorithm for finding a spanning tree with non-terminal set <i>V_NT</i> on cographs,” IEICE Trans. Inf. & Syst., vol.E99-D, no.10, pp.2574-2584, Oct. 2016. 10.1587/transinf.2016edp7021

タイトルに関連する用語 (6件)： 直列 ,  グラフ ,  集合 ,  最小スパンニング木 ,  発見 ,  線形時間アルゴリズム