On the Algorithmic Complexity of Total Domination

From MaRDI portal
Publication:3696538


DOI10.1137/0605040zbMath0576.68056MaRDI QIDQ3696538

Sandra M. Hedetniemi, Stephen T. Hedetniemi, Renu C. Laskar, John Pfaff

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0605040

zbMATH Keywords

tree; linear time algorithm; NP-complete; undirected path graphs; minimum total dominating sets


Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05-04: Software, source code, etc. for problems pertaining to combinatorics


Related Items

Total domination in interval graphs, Total domination in interval graphs, Domination in distance-hereditary graphs, The \(p\)-Maxian problem on interval graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, On the complexity of signed and minus total domination in graphs, A survey of selected recent results on total domination in graphs, \(k\)-tuple domination in graphs, A unified approach to domination problems on interval graphs, Labeling algorithms for domination problems in sun-free chordal graphs, Total domination in block graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, The complexity of domination problems in circle graphs, Dominating cliques in chordal graphs, On the computational complexity of upper total domination, The weighted perfect domination problem and its variants, Paired domination on interval and circular-arc graphs



Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3696538&oldid=17185890"
Powered by MediaWiki