New analysis and computational study for the planar connected dominating set problem
From MaRDI portal
Publication:328712
DOI10.1007/s10878-015-9871-0zbMath1354.90156OpenAlexW2013280510WikidataQ60402182 ScholiaQ60402182MaRDI QIDQ328712
Qian-Ping Gu, Marjan Marzban, Xiao-Hua Jia
Publication date: 20 October 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9871-0
planar graphscomputational studyconnected dominating setfixed-parameter algorithmsbranch-decomposition based algorithms
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate tree decompositions of planar graphs in linear time
- Fundamentals of parameterized complexity
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Subexponential parameterized algorithms
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Experiments on data reduction for optimal domination in networks
- Computational study on planar dominating set problem
- Graph minors. I. Excluding a forest
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Approximation algorithms for connected dominating sets
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Speeding Up Dynamic Programming with Representative Sets
- Planar Branch Decompositions I: The Ratcatcher
- Planar Branch Decompositions II: The Cycle Method
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Computational Study for Planar Connected Dominating Set Problem
- New upper bounds on the decomposability of planar graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
- Polynomial-time data reduction for dominating set
- Faster Algorithms on Branch and Clique Decompositions
- Linear Kernel for Planar Connected Dominating Set
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- On Hadwiger's Number and the Stability Number
- Graph minors. II. Algorithmic aspects of tree-width
- TSPLIB—A Traveling Salesman Problem Library
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
- Mathematical Foundations of Computer Science 2004
- Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
- Dynamic Programming and Fast Matrix Multiplication
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
