$Delta^p _2$Complete Lexicographically First - Collections

＜technical report＞
$Delta^p _2$Complete Lexicographically First

Creator	Author PID L001145 Creator Name Miyano, Satoru 宮野, 悟 Affiliation Affiliation Name Research Institute of Fundamental Information Science, Kyushu Uriiversity 九州大学理学部附属基礎情報学研究施設
Language	English
Publisher	Research Institute of Fundamental Information Science, Kyushu University
Publisher	九州大学理学部附属基礎情報学研究施設
Date	1987-12-07
Source Title	RIFIS Technical Report
Vol	1
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	RIFIS Technical Report \|\| 1 \|\| p1-16
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	RIFIS Technical Report \|\| 1 \|\| p1-16
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	RIFIS Technical Report \|\| 1 \|\| p1-16
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	The lerrtcographically first maximal (lfm) induced path problem is shown $ Delta ^p_2 $- complete. The lfm rooted tree problem is also analyzed. This problem is $ Delta^p_2 $- complete, But when restr...icted to topologically sorted directed acyclic graphs (dags), it allows a polynomial time algorithm. &Moreover, the problem restricted to topologically sorted Bags with degree 3 is shown in $ NC^2 $ while the problem for degree 4 is P-complete.show more

File	FileType	Size	Views	Description
rifis-tr-1	pdf	1.76 MB	202

Record ID	3107
Peer-Reviewed	Unrefereed
Notes	Proc. Mathematical Foundations of Computer Science 1988, Lecture Notes in Computer Science 324, 454-462, 1988; Theoretical Computer Science 88 (1991) 33-57
Type	テクニカルレポート
Created Date	2009.04.22
Modified Date	2017.01.20