Faster algorithms for vertex partitioning problems parameterized by clique-width

DOI10.1016/j.tcs.2014.03.024zbMath1419.05204arXiv1311.0224OpenAlexW2081971779MaRDI QIDQ2447760

Sang-il Oum, Martin Vatshelle, Sigve Hortemo Sæther

Publication date: 29 April 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingclique-widthparameterized complexityrank-widthgeneralized domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Star colouring of bounded degree graphs and regular graphs ⋮ Rank-width: algorithmic and structural results ⋮ When an optimal dominating set with given constraints exists ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Several notions of rank-width for countable graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Boolean-width of graphs
• Dominating sets for split and bipartite graphs
• Testing branch-width
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• The rank-width of the square grid
• Graph minors. X: Obstructions to tree-decomposition
• Proper interval vertex deletion
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The rank-width of edge-coloured graphs
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Obstructions to branch-decomposition of matroids
• Faster Algorithms on Branch and Clique Decompositions
• Simpler Parameterized Algorithm for OCT
• Dominating Sets in Chordal Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Practical algorithms on partial k-trees with an application to domination-like problems
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Interval Deletion is Fixed-Parameter Tractable
• Rank‐width is less than or equal to branch‐width
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Faster algorithms for vertex partitioning problems parameterized by clique-width