Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
From MaRDI portal
(Redirected from Publication:3434987)
Recommendations
Cited in
(63)- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- On parameterized exponential time complexity
- Computational study on planar dominating set problem
- Tree-length equals branch-length
- Computational study on a PTAS for planar dominating set problem
- Subexponential fixed-parameter algorithms for partial vector domination
- Twin-width and polynomial kernels
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Capacitated domination: problem complexity and approximation algorithms
- A refined search tree technique for dominating set on planar graphs
- (Total) vector domination for graphs with bounded branchwidth
- Graph minors and parameterized algorithm design
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Subexponential fixed-parameter algorithms for partial vector domination
- New analysis and computational study for the planar connected dominating set problem
- Capacitated Domination and Covering: A Parameterized Perspective
- 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
- Beyond bidimensionality: parameterized subexponential algorithms on directed 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
- scientific article; zbMATH DE number 2079336 (Why is no real title available?)
- scientific article; zbMATH DE number 1756013 (Why is no real title available?)
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- scientific article; zbMATH DE number 1929955 (Why is no real title available?)
- Parameterized complexity: exponential speed-up for planar graph problems
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Lossy Kernels for Hitting Subgraphs
- Subexponential parameterized algorithms for graphs of polynomial growth
- Mobile sensor networks: system hardware and dispatch software
- Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
- Parameterized complexity of directed Steiner tree on sparse graphs
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- STACS 2004
- Mathematical Foundations of Computer Science 2004
- Automata, Languages and Programming
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Dynamic programming for graphs on surfaces
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Dominating sets and local treewidth
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Improved induced matchings in sparse graphs
- A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
- Dominating set is fixed parameter tractable in claw-free graphs
- Fast FPT-approximation of branchwidth
- On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives
- Sidestepping barriers for dominating set in parameterized complexity
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Minimum-cardinality global defensive alliances in general graphs
- Face-hitting dominating sets in planar graphs
- Dominating sets in plane triangulations
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Residue domination in bounded-treewidth graphs
- Dominating set with quotas: balancing coverage and constraints
- Practical algorithms for branch-decompositions of planar graphs
- Computing branchwidth via efficient triangulations and blocks
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
This page was built for publication: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434987)
