Fast exact algorithms for some connectivity problems parameterized by clique-width

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

zbMATH Keywords

connected \(\sigma, \rho\)-domination

Mathematics Subject Classification ID

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