|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Min-Power Covering Problemsтезисы доклада
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Angel E., Bampis E., Chau V., Kononov A.
- Сборник: Algorithms and Computation. ISAAC 2015
- Серия: Lecture Notes in Computer Science
- Том: 9472
- Тезисы
- Год издания: 2015
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 367
- Последняя страница: 377
- DOI: 10.1007/978-3-662-48971-0_32
- Аннотация: 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 such that for every edge 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.
- Добавил в систему: Кононов Александр Вениаминович