Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs

DOI10.1007/978-3-642-02927-1_27MaRDI QIDQ3638044zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Ken-ichi Kawarabayashi, Mohammad T. Hajiaghayi

Publication date 14 July 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-02927-1_27

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 6297711
• Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
• Additive non-approximability of chromatic number in proper minor-closed classes
• scientific article; zbMATH DE number 1670877
• Additive non-approximability of chromatic number in proper minor-closed classes

Cited in

(12)

• Parameterized complexity of the spanning tree congestion problem
• Face covers and the genus problem for apex graphs
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Layered separators in minor-closed graph classes with applications
• Additive non-approximability of chromatic number in proper minor-closed classes
• scientific article; zbMATH DE number 5874803 (Why is no real title available?)
• Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• List-coloring graphs without subdivisions and without immersions
• Going beyond surfaces in diameter approximation

This page was built for publication: Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs

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