Bounded Degree Maximal Subgraph Problems are in NC - Collections

＜technical report＞
Bounded Degree Maximal Subgraph Problems are in NC

Creator	Author PID K000176 Creator Name Shoudai, Takayoshi 正代, 隆義 Affiliation Affiliation Name Department of Control Engineering and Science Kyushu Institute of Technology 九州工業大学情報工学部制御システム工学科
Creator	Author PID L001145 Creator Name Miyano, Satoru 宮野, 悟 Affiliation Affiliation Name Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設
Language	English
Publisher	Research Institute of Fundamental Information Science, Kyushu University
Publisher	九州大学理学部附属基礎情報学研究施設
Date	1990-07-07
Source Title	RIFIS Technical Report
Vol	27
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	RIFIS Technical Report \|\| 27 \|\| p1-6
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	RIFIS Technical Report \|\| 27 \|\| p1-6
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	RIFIS Technical Report \|\| 27 \|\| p1-6
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	We show that the problem of finding a maximal vertex-induced (resp., edge-induced) subgraph of maximum degree k is in $ NC^2 $ for $ k leq 0 (resp., k leq 1) $. For these problems, we develope a meth...od which exploits the NC algorithm for the maximal independent set problem.show more

File	FileType	Size	Views	Description
rifis-tr-27	pdf	930 KB	393

Record ID	3134
Peer-Reviewed	Unrefereed
Notes	Proc. Toyohashi Symposium on Theoretical Computer Science, 97-101
Type	テクニカルレポート
Created Date	2009.04.22
Modified Date	2017.01.20