Defending planar graphs against star-cutsets

DOI10.1016/J.ENDM.2009.07.018MaRDI QIDQ2851448zbMATH OpenOpenAlexFDO

Authors Nicolas Sonnerat, Adrian Vetta

Publication date 10 October 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.07.018

zbMATH Keywords

approximation algorithmsgraph connectivityplanar graphsstar-cutsets

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for NP-complete problems on planar graphs
• On finding two-connected subgraphs in planar graphs
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• scientific article; zbMATH DE number 177556
• The Complexity of Multiterminal Cuts

Cites work

• A threshold of ln n for approximating set cover
• Galaxy cutsets in graphs
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Skew partitions in perfect graphs
• Star-cutsets and perfect graphs
• The firefighter problem for graphs of maximum degree three

Cited in

(1)

• Galaxy cutsets in graphs

This page was built for publication: Defending planar graphs against star-cutsets

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