The Lexicographically First Topologicai Order Problem is NLOG-Complete - 九大コレクション

＜テクニカルレポート＞
The Lexicographically First Topologicai Order Problem is NLOG-Complete

作成者	著者識別子 K000176 作成者名 Shoudai, Takayoshi 正代, 隆義所属機関所属機関名 Department of Mathematics, Kyushu University 九州大学理学研究科
本文言語	英語
出版者	Research Institute of Fundamental Information Science, Kyushu University
出版者	九州大学理学部附属基礎情報学研究施設
発行日	1988-12-26
収録物名	RIFIS Technical Report
巻	8
出版タイプ	Accepted Manuscript
アクセス権	open access
関連DOI	RIFIS Technical Report \|\| 8 \|\| p1-7
関連DOI	http://www.i.kyushu-u.ac.jp/research/report.html
関連URI	RIFIS Technical Report \|\| 8 \|\| p1-7
関連URI	http://www.i.kyushu-u.ac.jp/research/report.html
関連情報	RIFIS Technical Report \|\| 8 \|\| p1-7
関連情報	http://www.i.kyushu-u.ac.jp/research/report.html
概要	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.

ファイル	ファイルタイプ	サイズ	閲覧回数	説明
rifis-tr-8	pdf	850 KB	409

レコードID	3114
査読有無	査読無
主題	Computational complexity
	topological sort
	NLOG-complete
注記	Information Processing Letters 33, 121-124, 1989
タイプ	テクニカルレポート
登録日	2009.04.22
更新日	2017.01.20