Complexity and lowers bounds for power edge set problem
From MaRDI portal
Publication:1711663
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
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
