Art

J-GLOBAL ID：201902243691929703   Reference number：19A1174930

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

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

Author (2)： NAKAYAMA Shin-ichi (Department of Science and Technology, Tokushima University) ,  MASUYAMA Shigeru (Department of Management, School of Management, Tokyo University of Science)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E102.D  Issue： 4  Page： 826-835(J-STAGE)  Publication year： 2019 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *spanning tree ,  *algorithm ,  NP hard ,  *graph ,  subset
Semi thesaurus term： *linear time algorithm

Author keywords (3)： spanning tree ,  series-parallel graph ,  algorithm

JST classification (1)： Basics of graph theory  (IA02020S)

Reference (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

Terms in the title (6)： 直列 ,  グラフ ,  集合 ,  最小スパンニング木 ,  発見 ,  線形時間アルゴリズム