2-Approximation algorithm for finding a spanning tree with maximum number of 
leaves

Solis-Oba, Roberto

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

2-Approximation algorithm for finding a spanning tree with maximum number of leaves

MPS-Authors

/persons/resource/persons45136

Solis-Oba, Roberto
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

MPI-I-98-1-010.pdf
(全文テキスト（全般）), 204KB

付随資料 (公開)

There is no public supplementary material available

引用

Solis-Oba, R.(1998). 2-Approximation algorithm for finding a spanning tree with maximum number of leaves (MPI-I-1998-1-010). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-7BD6-0

要旨

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple 2-approximation algorithm for the problem, improving on the previous best performance ratio of 3 achieved by algorithms of Ravi and Lu. Our algorithm can be implemented to run in linear time using simple data structures. We also study the variant of the problem in which a given subset of vertices are required to be leaves in the tree. We provide a 5/2-approximation algorithm for this version of the problem