Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems

DOI10.1016/j.tcs.2013.01.009zbMath1408.68111OpenAlexW2149785904MaRDI QIDQ392025

Martin Vatshelle, Binh-Minh Bui-Xuan, Jan Arne Telle

Publication date: 13 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.01.009

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Star colouring of bounded degree graphs and regular graphs ⋮ A new approach on locally checkable problems ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ Mim-width. I. Induced path problems ⋮ More results on weighted independent domination ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ When an optimal dominating set with given constraints exists ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the tractability of optimization problems on $H$-graphs ⋮ Finding perfect matching cuts faster ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ On $d$-stable locally checkable problems parameterized by mim-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of $(H_1,H_2)$-free graphs ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ List $k$-colouring $P_t$-free graphs: a mim-width perspective ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximum rooted connected expansion ⋮ Cluster deletion on interval graphs and split related graphs ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Unnamed Item ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ Distance Domination in Graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Boolean-Width of Graphs ⋮ New algorithms for weighted $k$-domination and total $k$-domination problems in proper interval graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Revising Johnson's table for the 21st century ⋮ 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 ⋮ A simple optimal algorithm for $k$-tuple dominating problem in interval graphs

Cites Work