Art

J-GLOBAL ID：201602239153321085   Reference number：16A1305844

A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set V_NT on Cographs

共同グラフの非終端セットV_NTを持つスパンニング木を見つけるための線形時間アルゴリズム

Author (2)： NAKAYAMA Shin-ichi (Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, Tokushima University) ,  MASUYAMA Shigeru (Department of Computer Science and Engineering, Toyohashi University of Technology)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E99.D  Issue： 10  Page： 2574-2584(J-STAGE)  Publication year： 2016 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： algorithm ,  *spanning tree ,  vertex ,  subset ,  edge ,  graph ,  leaf ,  integer ,  NP hard ,  property ,  *linear time algorithm ,  complexity
Semi thesaurus term： complexity

Author keywords (3)： spanning tree ,  cograph ,  algorithm

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

Reference (8)：

• [1] D.G. Corneil, H. Lerchs, and L.S. Burlingham, “Complement reducible graphs,” Discrete Applied Mathematics, vol.3, no.3, pp.163-174, 1981.
• [2] D.G. Corneil and Y. Perl, “Clustering and domination in perfect graphs,” Discrete Applied Mathematics, vol.9, no.1, pp.27-39, 1984.
• [3] D.G. Corneil, Y. Perl, and L.K. Stewart, “Cographs: Recognition, applications and algorithms,” Proc. Fifteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp.249-258, 1984.
• [4] D.G. Corneil, Y. Perl, and L. Stewart, “A linear recognition algorithm for cographs,” SIAM J. Comput., vol.14, no.4, pp.926-934, 1985.
• [5] M. Habib and C. Paul, “A simple linear time algorithm for cograph recognition,” Discrete Applied Mathematics, vol.145, no.2, pp.183-197, 2005.

Terms in the title (4)： 共同 ,  グラフ ,  スパンニング木 ,  線形時間アルゴリズム