Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
From MaRDI portal
Publication:3434987
DOI10.1137/S0097539702419649zbMath1114.05072WikidataQ60488760 ScholiaQ60488760MaRDI QIDQ3434987
Dimitrios M. Thilikos, Fedor V. Fomin
Publication date: 3 May 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Unnamed Item ⋮ Improved induced matchings in sparse graphs ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ On self-duality of branchwidth in graphs of bounded genus ⋮ The complexity of two graph orientation problems ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Subexponential parameterized algorithms ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Confronting intractability via parameters ⋮ Computational study on a PTAS for planar dominating set problem ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ Mobile Sensor Networks ⋮ Dominating sets in plane triangulations ⋮ Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ On parameterized exponential time complexity ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Planar Capacitated Dominating Set Is W[1-Hard] ⋮ Improved Induced Matchings in Sparse Graphs ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Computational study on planar dominating set problem ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Tree-length equals branch-length ⋮ Lossy Kernels for Hitting Subgraphs ⋮ Dynamic programming for graphs on surfaces ⋮ Twin-width and polynomial kernels ⋮ Unnamed Item ⋮ Capacitated domination: problem complexity and approximation algorithms
