Algorithm and hardness results on hop domination in graphs

DOI10.1016/j.ipl.2019.105872zbMath1481.05116OpenAlexW2980418712MaRDI QIDQ2338219

Yanyan Li

Publication date: 21 November 2019

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2019.105872

zbMATH Keywords

NP-completenesspolynomial-time algorithmgraph algorithmsdominationhop domination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

ON HOP DOMINATION NUMBER OF SOME GENERALIZED GRAPH STRUCTURES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bipartite permutation graphs with application to the minimum buffer size problem
• A linear time algorithm for optimal \(k\)-hop dominating set of a tree
• Bounds on the hop domination number of a tree
• Bipartite permutation graphs
• Optimization, approximation, and complexity classes
• On exact \(n\)-step domination
• Some APX-completeness results for cubic graphs
• A note: Some results in step domination of trees
• On 2-step and hop dominating sets in graphs
• A Greedy Heuristic for the Set-Covering Problem
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey
• Exact $2$-step domination in graphs
• Analytical approach to parallel repetition