TY - GEN
T1 - Min-Power Covering Problems
AU - Angel, Eric
AU - Bampis, Evripidis
AU - Chau, Vincent
AU - Kononov, Alexander
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2015
Y1 - 2015
N2 - In the classical vertex cover problem, we are given a graph G = (V, E) and we aim to find a minimum cardinality cover of the edges, i.e. a subset of the vertices C subset of V such that for every edge e is an element of E, at least one of its extremities belongs to C. In the Min-Power-Cover version of the vertex cover problem, we consider an edge-weighted graph and we aim to find a cover of the edges and a valuation (power) of the vertices of the cover minimizing the total power of the vertices. We say that an edge e is covered if at least one of its extremities has a valuation (power) greater than or equal than the weight of e. In this paper, we consider Min-Power-Cover variants of various classical problems, including vertex cover, min cut, spanning tree and path problems.
AB - In the classical vertex cover problem, we are given a graph G = (V, E) and we aim to find a minimum cardinality cover of the edges, i.e. a subset of the vertices C subset of V such that for every edge e is an element of E, at least one of its extremities belongs to C. In the Min-Power-Cover version of the vertex cover problem, we consider an edge-weighted graph and we aim to find a cover of the edges and a valuation (power) of the vertices of the cover minimizing the total power of the vertices. We say that an edge e is covered if at least one of its extremities has a valuation (power) greater than or equal than the weight of e. In this paper, we consider Min-Power-Cover variants of various classical problems, including vertex cover, min cut, spanning tree and path problems.
KW - NETWORKS
UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000375151300032
U2 - 10.1007/978-3-662-48971-0_32
DO - 10.1007/978-3-662-48971-0_32
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-3-662-48970-3
VL - 9472
T3 - Lecture Notes in Computer Science
SP - 367
EP - 377
BT - ALGORITHMS AND COMPUTATION, ISAAC 2015
PB - Springer
T2 - 26th International Symposium on Algorithms and Computation (ISAAC)
Y2 - 9 December 2015 through 11 December 2015
ER -