Minimum Power Dominating Sets of Random Cubic Graphs

DOI10.1002/jgt.22053zbMath1442.05162OpenAlexW2423480771MaRDI QIDQ5272639

Li-ying Kang, Nicholas C. Wormald

Publication date: 30 June 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.22053

zbMATH Keywords

random cubic graphspower domination

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Properties of regular graphs with large girth via local algorithms ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Power Domination in Graphs

Cites Work

• Properties of regular graphs with large girth via local algorithms
• Parameterized power domination complexity
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Improved algorithms and complexity results for power domination in graphs
• Approximation algorithms for combinatorial problems
• Analysis of greedy algorithms on graphs with bounded degrees
• Differential equations for random processes and random graphs
• Power domination in graphs
• A threshold of ln n for approximating set cover
• On the hardness of approximating minimization problems
• Domination in Graphs Applied to Electric Power Networks
• Minimum independent dominating sets of random cubic graphs
• Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs
• Approximation Algorithms and Hardness for Domination with Propagation

This page was built for publication: Minimum Power Dominating Sets of Random Cubic Graphs