Journal
ALGORITHMICA
Volume 63, Issue 1-2, Pages 137-157Publisher
SPRINGER
DOI: 10.1007/s00453-011-9523-4
Keywords
Series-parallel graph; Approximation algorithm
Funding
- NSF [CCF-0515088, NeTS-0916743, IIS-0916401]
- CNPq [312347/2006-5, 485671/2007-7, 486124/2007-0]
- NIFA [2011-67016-30331]
- Direct For Computer & Info Scie & Enginr
- Division Of Computer and Network Systems [0916743] Funding Source: National Science Foundation
- NIFA [2011-67016-30331, 579659] Funding Source: Federal RePORTER
Ask authors/readers for more resources
Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
