Maximum series-parallel subgraph

DOI10.1007/S00453-011-9523-4MaRDI QIDQ2429333zbMATH OpenOpenAlexFDO

Authors Gruia Calinescu, Cristina G. Fernandes, Hemanshu Kaul, Alex Zelikovsky

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9523-4

zbMATH Keywords

approximation algorithmseries-parallel graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Maximum series-parallel subgraph
• The maximum degree of series-parallel graphs
• On maximum common subgraph problems in series-parallel graphs
• On maximum common subgraph problems in series-parallel graphs
• Finding maximum common biconnected subgraphs in series-parallel graphs
• Generalized max flow in series-parallel graphs
• Minimum-maximal matching in series-parallel graphs
• Series-parallel subgraphs of planar graphs
• MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS
• Subgraphs of maximum matching graphs

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A new approximation algorithm for finding heavy planar subgraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved Approximations for the Steiner Tree Problem
• On spanning 2-trees in a graph
• On the SPANNING k-TREE problem

Cited in

(8)

• Maximum series-parallel subgraph
• A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph
• Exact algorithms for single-machine scheduling with time windows and precedence constraints
• Finding triangles for maximum planar subgraphs
• On the maximal number of leaves in induced subtrees of series-parallel graphs
• scientific article; zbMATH DE number 7559128 (Why is no real title available?)
• Series-parallel subgraphs of planar graphs
• scientific article; zbMATH DE number 841593 (Why is no real title available?)

This page was built for publication: Maximum series-parallel subgraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429333)