Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
From MaRDI portal
Publication:1849745
DOI10.1007/s00453-001-0116-5zbMath1016.68055OpenAlexW1983156760MaRDI QIDQ1849745
Henning Fernau, Rolf Niedermeier, Jochen Alber, Ton Kloks, Hans L. Bodlaender
Publication date: 1 December 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0116-5
planar graphstreewidthNP-complete problemsfixed parameter tractabilityouterplanarityface coverplanar dominating set
Related Items (79)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Improved exact algorithms for MAX-SAT ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Parameterized Complexity for Domination Problems on Degenerate Graphs ⋮ Strong computational lower bounds via parameterized complexity ⋮ Experiments on data reduction for optimal domination in networks ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ Unnamed Item ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ 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 ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ On the kernel and related problems in interval digraphs ⋮ The complexity of two graph orientation problems ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Exact algorithms for edge domination ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Parameterized domination in circle graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Subexponential parameterized algorithms ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Spanners in sparse graphs ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Computational study on a PTAS for planar dominating set problem ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Online dominating set ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Fast minor testing in planar graphs ⋮ Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm ⋮ Kernels in planar digraphs ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Improved bottleneck domination algorithms ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ Unnamed Item ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Tree-decompositions of small pathwidth ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Decomposition of Map Graphs with Applications. ⋮ The parameterized complexity of the induced matching problem ⋮ On parameterized exponential time complexity ⋮ Planar Capacitated Dominating Set Is W[1-Hard] ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Computational study on planar dominating set problem ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ A refined search tree technique for dominating set on planar graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Unnamed Item ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ On Complexities of Minus Domination ⋮ Tree Decompositions of Graphs: Saving Memory in Dynamic Programming ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ A generic convolution algorithm for join operations on tree decompositions
This page was built for publication: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
