Maximum Series-Parallel Subgraph
| Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
|---|---|
| Data(s) |
29/10/2013
29/10/2013
2012
|
| Resumo |
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. NSF NSF [CCF-0515088, NeTS-0916743, IIS-0916401] CNPq [312347/2006-5, 485671/2007-7, 486124/2007-0] CNPq NIFA [2011-67016-30331] NIFA |
| Identificador |
ALGORITHMICA, NEW YORK, v. 63, n. 41306, supl. 5, Part 3, pp. 137-157, JUN, 2012 0178-4617 http://www.producao.usp.br/handle/BDPI/36365 10.1007/s00453-011-9523-4 |
| Idioma(s) |
eng |
| Publicador |
SPRINGER NEW YORK |
| Relação |
ALGORITHMICA |
| Direitos |
restrictedAccess Copyright SPRINGER |
| Palavras-Chave | #SERIES-PARALLEL GRAPH #APPROXIMATION ALGORITHM #APPROXIMATION ALGORITHM #PLANAR SUBGRAPHS #TREE PROBLEM #COMPUTER SCIENCE, SOFTWARE ENGINEERING #MATHEMATICS, APPLIED |
| Tipo |
article original article publishedVersion |
