Defending Planar Graphs against Star-Cutsets

DOI10.1016/J.ENDM.2009.07.018zbMath1273.68412OpenAlexW2071917180MaRDI QIDQ2851448

Adrian Vetta, Nicolas Sonnerat

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

planar graphsgraph connectivityapproximation algorithmsstar-cutsets

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Galaxy cutsets in graphs
• Star-cutsets and perfect graphs
• The firefighter problem for graphs of maximum degree three
• Skew partitions in perfect graphs
• A threshold of ln n for approximating set cover

This page was built for publication: Defending Planar Graphs against Star-Cutsets