Approximating Minimum Common Supertrees for Complete k-Ary Trees - 九大コレクション

＜テクニカルレポート＞
Approximating Minimum Common Supertrees for Complete k-Ary Trees

作成者	作成者名 Yamaguchi, Atsuko 山口, 敦子所属機関所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設
作成者	著者識別子 L001145 作成者名 Miyano, Satoru 宮野, 悟所属機関所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設
本文言語	英語
出版者	Research Institute of Fundamental Information Science, Kyushu University
出版者	九州大学理学部附属基礎情報学研究施設
発行日	1993-03-25
収録物名	RIFIS Technical Report
巻	66
出版タイプ	Accepted Manuscript
アクセス権	open access
関連DOI	RIFIS Technical Report \|\| 66 \|\| p1-8
関連DOI	http://www.i.kyushu-u.ac.jp/research/report.html
関連URI	RIFIS Technical Report \|\| 66 \|\| p1-8
関連URI	http://www.i.kyushu-u.ac.jp/research/report.html
関連情報	RIFIS Technical Report \|\| 66 \|\| p1-8
関連情報	http://www.i.kyushu-u.ac.jp/research/report.html
概要	For a set T of complete k-ary trees, we give a polynomial-time approximation algorithm for the problem of finding a k-ary common supertree with the minimum number of edges. This algorithm constructs a... common supertree that has at most (5/3)l edges, where l is the number of edges in a minimum common supertree if $ k leq 2 $.続きを見る

ファイル	ファイルタイプ	サイズ	閲覧回数	説明
rifis-tr-66	pdf	592 KB	143