Independent dominating set problem revisited
DOI10.1016/J.TCS.2014.09.001zbMATH Open1303.68073OpenAlexW1985099784WikidataQ62041723 ScholiaQ62041723MaRDI QIDQ476836FDOQ476836
Authors: Ching-Hao Liu, Sheung-Hung Poon, Jin-Yong Lin 
Publication date: 2 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.001
Recommendations
- NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
- Algorithmic aspects of some variants of domination in graphs
- A branch-and-reduce algorithm for finding a minimum independent dominating set
- On approximating the minimum independent dominating set
- A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
dominating setNP-completeindependent dominating set\((k,\ell)\)-graphat-most-cubic grid graphcubic bipartite graphFPT-algorithmweighted independent dominating set
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Clustering and domination in perfect graphs
- Unit disk graphs
- The Problem of Compatible Representatives
- Approximation algorithms for NP-complete problems on planar graphs
- On approximating the minimum independent dominating set
- Title not available (Why is that?)
- Dominating sets for split and bipartite graphs
- On the hardness of approximating minimization problems
- Independent domination on tree convex bipartite graphs
- Polynomial-time data reduction for dominating set
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Independent domination in chordal graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Title not available (Why is that?)
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- An induced subgraph characterization of domination perfect graphs
- Optimal binary space partitions for segments in the plane
Cited In (11)
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- Independent strong weak domination: A mathematical programming approach
- Algorithmic results of independent \(k\)-domination on weighted graphs
- NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- On the kernel and related problems in interval digraphs
- On the independent dominating set polytope
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- Algorithmic aspects of some variants of domination in graphs
- Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs
- A branch-and-reduce algorithm for finding a minimum independent dominating set
This page was built for publication: Independent dominating set problem revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476836)
