Premium
Covering edges in networks
Author(s) -
Fröhlich Nicolas,
Maier Andrea,
Hamacher Horst W.
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21924
Subject(s) - cover (algebra) , time complexity , focus (optics) , vertex cover , edge cover , enhanced data rates for gsm evolution , set cover problem , combinatorics , greedy algorithm , mathematics , dominating set , approximation algorithm , computer science , set (abstract data type) , computational complexity theory , finite set , task (project management) , mathematical optimization , discrete mathematics , algorithm , graph , artificial intelligence , vertex (graph theory) , mechanical engineering , physics , optics , programming language , engineering , mathematical analysis , management , economics
Abstract In this paper we consider the covering problem on a network G = ( V , E ) with edge demands. The task is to cover a subset J ⊆ E of the edges with a minimum number of facilities within a predefined coverage radius. We focus on both the nodal and the absolute version of this problem. In the latter, facilities may be placed everywhere in the network. While there already exist polynomial time algorithms to solve the problem on trees, we establish a finite dominating set (i.e., a finite subset of points provably containing an optimal solution) for the absolute version in general graphs. Complexity and approximability results are given and a greedy strategy is proved to be a (1 + ln(| J |))‐approximate algorithm. Finally, the different approaches are compared in a computational study.