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

• A Better Approximation Algorithm for Finding Planar Subgraphs
• A new approximation algorithm for finding heavy planar subgraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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?)
• Improved Approximations for the Steiner Tree Problem
• On spanning 2-trees in a graph
• On the SPANNING k-TREE problem

Cited in

(11)

• Finding triangles for maximum planar subgraphs
• Exact algorithms for single-machine scheduling with time windows and precedence constraints
• Series-parallel subgraphs of planar graphs
• scientific article; zbMATH DE number 841593 (Why is no real title available?)
• A tight extremal bound on the Lovász cactus number in planar graphs
• Maximum series-parallel subgraph
• A (1/2+1/60)-approximation algorithm for maximum weight series-parallel subgraph
• On the maximal number of leaves in induced subtrees of series-parallel graphs
• Local optimization algorithms for maximum planar subgraph
• Parameterised distance to local irregularity
• Parameterised distance to local irregularity

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)