2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of 
Leaves

Solis-Oba, Roberto

Local TagsRelease HistoryDetailsSummary

2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves

Solis-Oba, R. (1998). 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. In G. Bilardi, G. F. Italiano, A. Pietracaprina, & G. Pucci (Eds.), Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98) (pp. 441-452). Berlin, Germany: Springer.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-373E-5 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3740-E

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Solis-Oba, Roberto¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

Abstract: The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approximation algorithm for the problem is presented. The variant of the problem in which a given set of vertices must be leaves of the spanning tree is also studied. A 5/2-approximation algorithm for this version of the problem is presented.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1998

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: eDoc: 517935
Other: Local-ID: C1256428004B93B8-B3EB5125921E3007C1256682003ABC6D-Solis-Oba1998a

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Venice, Italy

Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show

hide

Title: Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)

Source Genre: Proceedings

Creator(s):
Bilardi, Gianfranco, Editor
Italiano, Giuseppe F., Editor
Pietracaprina, Andrea, Editor
Pucci, Geppino, Editor

Affiliations:
-

Publ. Info: Berlin, Germany : Springer

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 441 - 452 Identifier: -

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 1461 Sequence Number: - Start / End Page: - Identifier: -