Complexity and lowers bounds for power edge set problem

DOI10.1016/j.jda.2018.11.006zbMath1410.68292OpenAlexW2901328479WikidataQ128950224 ScholiaQ128950224MaRDI QIDQ1711663

Rodolphe Giroudeau, Nicolas Champseix, Mathias Weller, Annie Chateau, Benoit Darties

Publication date: 18 January 2019

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.11.006

zbMATH Keywords

complexityapproximation algorithmtreewidthphasor measurement unitpower edge set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Improved algorithms and complexity results for power domination in graphs
• Optimization, approximation, and complexity classes
• Which problems have strongly exponential complexity?
• Improved complexity for power edge set problem
• New insights for power edge set problem
• A note on power domination in grid graphs
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• Observing the State of a Smart Grid Using Bilevel Programming
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• Approximation algorithms for NP-complete problems on planar graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• The power edge set problem
• Domination in Graphs Applied to Electric Power Networks
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• On the complexity of \(k\)-SAT