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

NAKAYAMA Shin-ichi; MASUYAMA Shigeru

文献

J-GLOBAL ID：201602239153321085 整理番号：16A1305844

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

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

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=16A1305844&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=16A1305844&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (2件)： ,
資料名：
巻： E99.D 号： 10 ページ： 2574-2584(J-STAGE) 発行年： 2016年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

非終端セットと呼ばれる頂点のサブセットV_NTで指定された,VおよびEがそれぞれ頂点と端部セットであるグラフG=(V,E)を与えた,非終端セットV_NTを持つスパンニング木は,非終端セットの各頂点が葉ではないVの頂点全てを含むGの連結されたそして非環式スパンニング部分グラフである。各端部が非負整数の重みを持つ場合,Gの非終端セットV_NTを持つ最小スパンニング木を見つける問題は,NP困難であることが知られている。しかしながら,各端部が1の重みを持つ一般的なグラフのスパンニング木を見つけることの複雑さは未知であった。本論文では,著者らはこの問題を考察し,そして最初に各端部が一般的グラフ上で1の重みを持つ場合でもそれがNP困難であることを示した。著者らはまた,Gが共同グラフである場合,その時Gの非終端セットV_NTを持つスパンニング木を見つけることは,各端部が1の重みを持つ時直線的に解くことができることを示した。(翻訳著者抄録)

, , , , , , , , , , ,

著者キーワード (3件)： , ,

グラフ理論基礎

引用文献 (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.

, , ,

前のページに戻る

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

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