Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Min-Power Covering Problems
verfasst von : Eric Angel, Evripidis Bampis, Vincent Chau, Alexander Kononov
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \subseteq V\) such that for every edge \(e \in 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.