New Insights for Power Edge Set Problem
| Affiliation auteurs | !!!! Error affiliation !!!! |
| Titre | New Insights for Power Edge Set Problem |
| Type de publication | Conference Paper |
| Year of Publication | 2017 |
| Auteurs | Darties B, Chateau A, Giroudeau R, Weller M |
| Editor | Gao X, Du H, Han M |
| Conference Name | COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I |
| Publisher | Shanghai Jiao Tong Univ, Adv Network Lab; Nanjing Univ, GPS Lab; Shanghai Univ Finance & Econ, Res Inst Interdisciplinary Sci; Cardinal Operat Co |
| Conference Location | GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND |
| ISBN Number | 978-3-319-71150-8; 978-3-319-71149-2 |
| Résumé | We study the computational complexity of Power Edge Set (PES), for restricted graph classes with degree bounded by three (bipartite graph, Unit disk graphs and Grid graphs). This problem is devoted to the monitoring of an electric network. The aim is to minimize the number of edge-allocated PMUs in a network such that all vertices are monitored according to two spreading rules. We improve known complexity results using an L-reduction. We also derive some lowers bounds according to classic complexity hypothesis (P not equal NP, UGC, ETH). |
| DOI | 10.1007/978-3-319-71150-8_17 |