Power domination in circular-arc graphs

DOI10.1007/s00453-011-9599-xzbMath1259.05130OpenAlexW2013358561MaRDI QIDQ1939660

Chung-Shou Liao, Der-Tsai Lee

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9599-x

zbMATH Keywords

dominationinterval graphspower dominationcircular-arc graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Power domination in the generalized Petersen graphs ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ Power domination in certain chemical structures ⋮ Generalized power domination: propagation radius and Sierpiński graphs ⋮ Power domination with bounded time constraints ⋮ \(k\)-power domination in block graphs ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restricted power domination and fault-tolerant power domination on grids
• Parameterized power domination complexity
• Improved algorithms and complexity results for power domination in graphs
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• A linear-time algorithm for a special case of disjoint set union
• A unified approach to domination problems on interval graphs
• Linear time algorithms on circular-arc graphs
• \(k\) best cuts for circular-arc graphs
• A note on power domination in grid graphs
• Power domination in graphs
• Power domination in block graphs
• Minimum Cuts for Circular-Arc Graphs
• Power Domination in $\mathcal{O}^*(1.7548^n)$ Using Reference Search Trees
• Power Domination in Product Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Domination in Graphs Applied to Electric Power Networks
• The PMU Placement Problem
• Computing and Combinatorics
• Approximation Algorithms and Hardness for Domination with Propagation

This page was built for publication: Power domination in circular-arc graphs