Fast exact algorithms for some connectivity problems parameterized by clique-width
From MaRDI portal
Publication:2420640
DOI10.1016/j.tcs.2019.02.030zbMath1423.68328arXiv1707.03584OpenAlexW2963390736MaRDI QIDQ2420640
Benjamin Bergougnoux, Mamadou Moustapha Kanté
Publication date: 6 June 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.03584
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (5)
On the terminal connection problem ⋮ On the computational difficulty of the terminal connection problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Feedback vertex set on graphs of low clique-width
- Upper bounds to the clique width of graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Handle-rewriting hypergraph grammars
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Approximating clique-width and branch-width
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Graph minors. II. Algorithmic aspects of tree-width
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Approximating rank-width and clique-width quickly
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- On the complexity of \(k\)-SAT
This page was built for publication: Fast exact algorithms for some connectivity problems parameterized by clique-width
