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
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
