Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs

DOI10.1007/978-3-540-73420-8_10MaRDI QIDQ5428800zbMATH OpenOpenAlexFDO

Authors André Berger, Michelangelo Grigni

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_10

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Algorithms – ESA 2005
• Minimum 2-edge connected spanning subgraph of certain graphs
• Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
• On Minimum Spanning Subgraphs of Graphs With Proper Connection Number 2
• Edge-disjoint minimum-weight connected spanning \(k\)-edge subgraphs in a weighted graph: A connectedness theorem
• Minimum-weight two-connected spanning networks
• 2-connected spanning subgraphs of planar 3-connected graphs
• On the minimum weight of a 3-connected 1-planar graph
• 2-connected spanning subgraphs with low maximum degree in locally planar graphs
• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem

Cited in

(12)

• 2-connected spanning subgraphs of planar 3-connected graphs
• On the two-connected planar spanning subgraph polytope
• Edge-disjoint minimum-weight connected spanning \(k\)-edge subgraphs in a weighted graph: A connectedness theorem
• scientific article; zbMATH DE number 64356 (Why is no real title available?)
• scientific article; zbMATH DE number 742959 (Why is no real title available?)
• A PTAS for three-edge-connected survivable network design in planar graphs
• Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
• Minimum face-spanning subgraphs of plane graphs
• Algorithms – ESA 2005
• Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
• Correlation clustering and two-edge-connected augmentation for planar graphs
• Approximation schemes for planar graph connectivity problems

This page was built for publication: Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs

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