When an optimal dominating set with given constraints exists

DOI10.1016/j.tcs.2019.02.012zbMath1423.68338OpenAlexW2915433562WikidataQ128345324 ScholiaQ128345324MaRDI QIDQ2420615

Mohammadreza Hooshmandasl, Reza Naserasr, Omid Etesami, Pouyeh Sharifani, Narges Ghareghani, Michel A. Habib

Publication date: 6 June 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.02.012

zbMATH Keywords

dominating setNP-hardnessinterval graphspermutation graphstotal dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A note on bipartite graphs whose [1,k-domination number equal to their number of vertices] ⋮ \([1,k\)-domination number of lexicographic products of graphs]

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \((1, j)\)-set problem in graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• \([1,2\)-domination in graphs]
• \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms]
• \([1,2\)-sets in graphs]
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Quasiperfect domination in triangular lattices
• The complexity of satisfiability problems