Complexity and inapproximability results for the power edge set problem

DOI10.1007/S10878-017-0241-YMaRDI QIDQ1743493zbMATH OpenOpenAlexFDO

Authors Sonia Toubaline, Claudia D'Ambrosio, Leo Liberti, Pierre-Louis Poirion, Baruch Schieber, Hadas Shachnai

Publication date 13 April 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0241-y

zbMATH Keywords

inapproximabilityNP-hardnessPMU placement problempower edge set

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Complexity and lowers bounds for power edge set problem
• Improved complexity for power edge set problem
• New insights for power edge set problem
• Approximation hardness of edge dominating set problems
• The power edge set problem
• Inapproximability of dominating set on power law graphs
• On the algorithmic complexity of edge total domination
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• Hardness Results and Efficient Algorithms for Graph Powers
• scientific article; zbMATH DE number 3889547

Cites work

• A note on power domination in grid graphs
• Approximation Algorithms and Hardness for Domination with Propagation
• Domination in Graphs Applied to Electric Power Networks
• Fundamentals of Computation Theory
• On Syntactic versus Computational Views of Approximability
• On the hardness of approximating minimum vertex cover
• Optimal covering of cacti by vertex-disjoint paths
• Power domination in block graphs
• The PMU Placement Problem
• The power edge set problem
• Zero forcing sets and the minimum rank of graphs

Cited in

(7)

• Improved complexity for power edge set problem
• New insights for power edge set problem
• Complexity and lowers bounds for power edge set problem
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• The power edge set problem
• The PMU Placement Problem
• Parameterized algorithms for power edge set and zero forcing set

This page was built for publication: Complexity and inapproximability results for the power edge set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1743493)