The Lexicographically First Topologicai Order Problem is NLOG-Complete - Collections

＜technical report＞
The Lexicographically First Topologicai Order Problem is NLOG-Complete

Creator	Author PID K000176 Creator Name Shoudai, Takayoshi 正代, 隆義 Affiliation Affiliation Name Department of Mathematics, Kyushu University 九州大学理学研究科
Language	English
Publisher	Research Institute of Fundamental Information Science, Kyushu University
Publisher	九州大学理学部附属基礎情報学研究施設
Date	1988-12-26
Source Title	RIFIS Technical Report
Vol	8
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	RIFIS Technical Report \|\| 8 \|\| p1-7
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	RIFIS Technical Report \|\| 8 \|\| p1-7
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	RIFIS Technical Report \|\| 8 \|\| p1-7
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	We show that the lexicogrsphically first topological order problem is NLOG - complete. The algorithm presented here uses the result that NLOG is closed under complementation.

File	FileType	Size	Views	Description
rifis-tr-8	pdf	850 KB	433

Record ID	3114
Peer-Reviewed	Unrefereed
Subject Terms	Computational complexity
	topological sort
	NLOG-complete
Notes	Information Processing Letters 33, 121-124, 1989
Type	テクニカルレポート
Created Date	2009.04.22
Modified Date	2017.01.20