|
|||||
|
|
Maximum Series-Parallel Subgraph |
|
| Authors: | Gruia C?linescu Cristina G Fernandes Hemanshu Kaul Alexander Zelikovsky |
| Affiliation: | 1. Department of Computer Science, Illinois Institute of Technology, Chicago, IL, 60616, USA 2. Department of Computer Science, University of S?o Paulo, Rua do Mat?o, 1010, 05508-090, S?o Paulo, Brazil 3. Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, 60616, USA 4. Department of Computer Science, Georgia State University, Atlanta, GA, 30303, USA |
| Abstract: | 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 $\frac{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 $\frac{7}{12}$ -approximation for this problem and results showing the limits of our approach. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |