MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Solis-Oba, Robertodblp
Editor(s):
Bilardi, Gianfranco
Italiano, Giuseppe F.
Pietracaprina, Andrea
Pucci, Geppino		dblp
dblp
dblp
dblp
BibTeX cite key*:
Solis-Oba1998a
Title, Booktitle
Title*:
2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
Booktitle*:
Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)
Event, URLs
Conference URL::
http://www.dsi.unive.it/~esa98
Downloading URL:
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
August 1998
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1461
Number:
Month:
August
Pages:
441-452
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Approximation algorithm, spanning tree, NP-hard
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Solis-Oba1998a,
AUTHOR = {Solis-Oba, Roberto},
 EDITOR = {Bilardi, Gianfranco and Italiano, Giuseppe F. and Pietracaprina, Andrea and Pucci, Geppino},
 TITLE = {2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves},
 BOOKTITLE = {Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1461},
 PAGES = {441--452},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Venice, Italy},
 MONTH = {August},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Roberto Solis-Oba		Created
09/17/1998 12:41:33 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
03/02/2010 05:40:51 PM
29.03.99 16:51:51
29.03.99 16:38:07
29.03.99 16:37:26
17/09/98 12:41:33