Complexity of finding k-path-free dominating sets in graphs

DOI10.1016/0020-0190(82)90021-7zbMath0491.68043OpenAlexW2089836190MaRDI QIDQ1167535

Reuven Bar Yehuda, Uzi Vishkin

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90021-7

zbMATH Keywords

NP-completenessdirected graphsatisfiability problemgraph algorithmstournamentdominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Problems and methods with multiple objective functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item