On the complexity of approximating the Hadwiger number

DOI10.1016/J.TCS.2008.12.020MaRDI QIDQ1006087zbMATH OpenOpenAlexFDO

Authors Martin Wahlen

Publication date 17 March 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.12.020

zbMATH Keywords

approximationgraph minorsHadwiger number

Mathematics Subject Classification ID

Graph minors (05C83) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1206797
• Complexity of approximation problems
• scientific article; zbMATH DE number 1670534
• On the approximation complexity hierarchy
• The relative complexity of approximate counting problems
• Towards hardness of approximation for polynomial time problems
• On the parameterized complexity of approximate counting
• Computation of Hadwiger number and related contraction problems. Tight lower bounds
• scientific article; zbMATH DE number 5130830
• The complexity of polynomial-time approximation

Cites work

• Approximating the maximum clique minor and some subgraph homeomorphism problems

Cited in

(6)

• Approximating the maximum clique minor and some subgraph homeomorphism problems
• Connected matchings in chordal bipartite graphs
• scientific article; zbMATH DE number 5130830 (Why is no real title available?)
• Approximating permanents and hafnians
• Computation of Hadwiger number and related contraction problems. Tight lower bounds
• A polynomial-time approximation algorithm for complete interval minors

This page was built for publication: On the complexity of approximating the Hadwiger number

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