Complexity and lowers bounds for power edge set problem

DOI10.1016/J.JDA.2018.11.006MaRDI QIDQ1711663zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Champseix, Annie Chateau, Rodolphe Giroudeau, Mathias Weller, B. 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

approximation algorithmcomplexityphasor measurement unitpower edge settreewidth

Mathematics Subject Classification ID

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

Recommendations

• Complexity and inapproximability results for the power edge set problem
• Improved complexity for power edge set problem
• New insights for power edge set problem
• The power edge set problem
• scientific article; zbMATH DE number 3889547
• Lower Bounds on Edge Searching
• On the algorithmic complexity of edge total domination
• Approximation hardness of edge dominating set problems

Cites work

• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A note on power domination in grid graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for NP-complete problems on planar graphs
• Domination in Graphs Applied to Electric Power Networks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1989701 (Why is no real title available?)
• Improved algorithms and complexity results for power domination in graphs
• Improved complexity for power edge set problem
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Lower bounds based on the exponential time hypothesis
• New insights for power edge set problem
• Observing the state of a smart grid using bilevel programming
• On the complexity of k-SAT
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Solving the connected dominating set problem and power dominating set problem by integer programming
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• The power edge set problem
• Which problems have strongly exponential complexity?

Cited in

(6)

• Improved complexity for power edge set problem
• New insights for power edge set problem
• Complexity and inapproximability results for the power edge set problem
• Power Edge Set and Zero Forcing Set remain difficult in cubic graphs
• The power edge set problem
• Parameterized algorithms for power edge set and zero forcing set

This page was built for publication: Complexity and lowers bounds for power edge set problem

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