Hardness of computing width parameters based on branch decompositions over the vertex set
From MaRDI portal
Publication:5890909
DOI10.1016/j.endm.2015.06.041zbMath1346.05238OpenAlexW2179984694MaRDI QIDQ5890909
Martin Vatshelle, Sigve Hortemo Sæther
Publication date: 14 October 2016
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2015.06.041
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- The parameterized complexity of the induced matching problem
- Induced matchings
- Call routing and the ratcatcher
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Clique-Width is NP-Complete
- Complexity of Finding Embeddings in a k-Tree
- Approximating rank-width and clique-width quickly
