New analysis and computational study for the planar connected dominating set problem
type: Item
instance of: scholarly article
title: New analysis and computational study for the planar connected dominating set problem
zbMATH Open document ID: 1354.90156
author: Marjan Marzban
author: Qian-Ping Gu
author: X.-H. Jia
published in: Journal of Combinatorial Optimization
publication date: 2016-10-20T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6641535
zbMATH Keywords: branch-decomposition based algorithms
zbMATH Keywords: connected dominating set
zbMATH Keywords: planar graphs
zbMATH Keywords: fixed-parameter algorithms
zbMATH Keywords: computational study
Wikidata QID: Q60402182
describes a project that uses: PIGALE
describes a project that uses: LEDA
describes a project that uses: TSPLIB
MaRDI profile type: Publication
full work available at URL: s10878-015-9871-0
OpenAlex ID: W2013280510
cites work: Polynomial-time data reduction for dominating set
cites work: Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
cites work: Experiments on data reduction for optimal domination in networks
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
cites work: Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
cites work: Q5692521
cites work: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
cites work: Faster Algorithms on Branch and Clique Decompositions
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
cites work: Dynamic Programming and Fast Matrix Multiplication
cites work: Subexponential parameterized algorithms
cites work: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
cites work: Catalan structures and dynamic programming in \(H\)-minor-free graphs
cites work: Q4027320
cites work: Fundamentals of parameterized complexity
cites work: On Hadwiger's Number and the Stability Number
cites work: Speeding Up Dynamic Programming with Representative Sets
cites work: Mathematical Foundations of Computer Science 2004
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: New upper bounds on the decomposability of planar graphs
cites work: Q4198056
cites work: Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
cites work: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
cites work: Approximation algorithms for connected dominating sets
cites work: Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
cites work: Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
cites work: Q4368728
cites work: Planar branch decompositions. I: The ratcatcher
cites work: Planar branch decompositions. II: The cycle method
cites work: Approximate tree decompositions of planar graphs in linear time
cites work: Call routing and the ratcatcher
cites work: Linear Kernel for Planar Connected Dominating Set
cites work: Computational study on planar dominating set problem
cites work: Computational Study for Planar Connected Dominating Set Problem
cites work: TSPLIB—A Traveling Salesman Problem Library
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
DOI: 10.1007/S10878-015-9871-0
description: scientific article; zbMATH DE number 6641535