The complexity of the vertex-minor problem

DOI10.1016/j.ipl.2021.106222OpenAlexW3216353401MaRDI QIDQ2059901

Jonas Helsen, Axel Dahlberg, Stephanie 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)

Related Items

Scattered Classes of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Circle graphs and monadic second-order logic
• Graph minors. I. Excluding a forest
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• S-functions for graphs
• Circle graph obstructions
• Computing small pivot-minors
• Algorithmic graph theory and perfect graphs
• Rank-width: algorithmic and structural results
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Über eine Eigenschaft der ebenen Komplexe
• Circle graph obstructions under pivoting
• Transforming graph states using single-qubit operations
• Reducibility among Combinatorial Problems