Systematized Approaches to the Complexity of Subgraph Problems - Collections

＜technical report＞
Systematized Approaches to the Complexity of Subgraph Problems

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-04-09
Source Title	RIFIS Technical Report
Vol	25
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	RIFIS Technical Report \|\| 25 \|\| p1-18
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	RIFIS Technical Report \|\| 25 \|\| p1-18
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	RIFIS Technical Report \|\| 25 \|\| p1-18
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	This is a survey on complexity issues of subgraph problems proved in a systematic way. We deal with vertex-deletion and edge-deletion problems which can be viewed as subgraph problems. General NP-comp...leteness theorems are presernted for these problems. We also present a systematized result which shoaws polynomial time algorithms for these problems restricted to series-parallel graphs. Another problem we consider in this paper is the lelxicographically first maximal subgraph problems which appear in connection with parallel complexity theory.show more

File	FileType	Size	Views	Description
rifis-tr-25	pdf	1.98 MB	274