The complexity of the vertex-minor problem

DOI10.1016/J.IPL.2021.106222OpenAlexW3216353401MaRDI QIDQ2059901FDOQ2059901

Authors Axel Dahlberg, Jonas Helsen, S. Wehner

Publication date 14 December 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.05689

zbMATH Keywords

computational complexityNP-completevertex-minorcircle graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The algorithmic complexity of minus domination in graphs
• The MIN-cut and vertex separator problem
• The complexity of induced minors and related problems
• The complexity of some graph problems with bounded minors of their constraint matrices
• The Complexity of Vertex Enumeration Methods
• scientific article; zbMATH DE number 795221
• The algorithmic complexity of the minus clique-transversal problem
• On the hardness of approximating minimum vertex cover
• The complexity of the minimum \(k\)-cover problem
• The complexity of minimum-length path decompositions

Cites work

• scientific article; zbMATH DE number 3523580 (Why is no real title available?)
• scientific article; zbMATH DE number 3361902 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Approximating clique-width and branch-width
• Circle graph obstructions
• Circle graph obstructions under pivoting
• Circle graphs and monadic second-order logic
• Computing small pivot-minors
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Graph minors. I. Excluding a forest
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Rank-width and vertex-minors
• Rank-width: algorithmic and structural results
• Reducibility among combinatorial problems
• S-functions for graphs
• Transforming graph states using single-qubit operations
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(4)

• The complexity of the vertex-minor problem
• Vertex-minors of graphs: a survey
• The algorithmic complexity of the minus clique-transversal problem
• Scattered classes of graphs

This page was built for publication: The complexity of the vertex-minor problem

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