Covering edges in networks
- In this paper we consider the covering problem on a networkG=(V,E)withedgedemands. The task is to cover a subsetJ⊆Eof the edges with a minimum numberof facilities within a predefined coverage radius. We focus on both the nodal andthe absolute version of this problem. In the latter, facilities may be placed every-where in the network. While there already exist polynomial time algorithms to solvethe problem on trees, we establish a finite dominating set (i.e., a finite subset ofpoints provably containing an optimal solution) for the absolute version in generalgraphs. Complexity and approximability results are given and a greedy strategy isproved to be a (1+ln(|J|))-approximate algorithm. Finally, the different approachesare compared in a computational study.
Verfasser*innenangaben: | Nicolas FröhlichORCiD, Andrea Maier, Horst W. Hamacher |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-79631 |
DOI: | https://doi.org/10.1002/net.21924 |
ISSN: | 1097-0037 |
Titel des übergeordneten Werkes (Englisch): | Networks |
Verlag: | Wiley |
Dokumentart: | Wissenschaftlicher Artikel |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 08.04.2024 |
Jahr der Erstveröffentlichung: | 2019 |
Veröffentlichende Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Datum der Publikation (Server): | 08.04.2024 |
Ausgabe / Heft: | 75/3 |
Seitenzahl: | 13 |
Erste Seite: | 278 |
Letzte Seite: | 290 |
Quelle: | https://onlinelibrary.wiley.com/doi/10.1002/net.21924 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Sammlungen: | Open-Access-Publikationsfonds |
Lizenz (Deutsch): | Zweitveröffentlichung |