Independent dominating set problem revisited
type: Item
instance of: scholarly article
title: Independent dominating set problem revisited
zbMATH Open document ID: 1303.68073
author: Ching-Hao Liu
author: Sheung-Hung Poon
author: Jin-Yong Lin
published in: Theoretical Computer Science
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6375964
zbMATH Keywords: NP-complete
zbMATH Keywords: FPT-algorithm
zbMATH Keywords: independent dominating set
zbMATH Keywords: dominating set
zbMATH Keywords: weighted independent dominating set
zbMATH Keywords: cubic bipartite graph
zbMATH Keywords: at-most-cubic grid graph
zbMATH Keywords: \((k,\ell)\)-graph
Wikidata QID: Q62041723
MaRDI profile type: Publication
full work available at URL: j.tcs.2014.09.001
OpenAlex ID: W1985099784
cites work: Polynomial-time data reduction for dominating set
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Dominating sets for split and bipartite graphs
cites work: The weighted independent domination problem is NP-complete for chordal graphs
cites work: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
cites work: Approximation hardness of dominating set problems in bounded degree graphs
cites work: Unit disk graphs
cites work: Clustering and domination in perfect graphs
cites work: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
cites work: OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
cites work: Q4393480
cites work: Q4526990
cites work: Independent domination in chordal graphs
cites work: Q4198056
cites work: On approximating the minimum independent dominating set
cites work: The Problem of Compatible Representatives
cites work: On the hardness of approximating minimization problems
cites work: On the algorithmic complexity of twelve covering and independence parameters of graphs
cites work: Optimization, approximation, and complexity classes
cites work: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
cites work: Independent Domination on Tree Convex Bipartite Graphs
cites work: An induced subgraph characterization of domination perfect graphs
DOI: 10.1016/J.TCS.2014.09.001
description: scientific article; zbMATH DE number 6375964