Nicolas Fröhlich
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Nicolas Fröhlich has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
Andrea Maier
Department of Mathematics,Technische Universität Kaiserslautern Germany
1 shared publicationHorst W. Hamacher
Department of Mathematics,Technische Universität Kaiserslautern Germany
1 shared publication- José Rui Figueira
CEGIST, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
1 shared publication - Luca E. Schäfer
Department of Mathematics Technische Universität Kaiserslautern 67663 Kaiserslautern Germany
1 shared publication Stefan Ruzika
1 shared publication- Stefan Ruzika
Department of Mathematics, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, 67663 Kaiserslautern, Germany
1 shared publication
Latest Publications
- Open Access
- 10 May 2021
- Published by Springer Nature in TOP
- Vol. 30 (1) , 95-118
Interdicting facilities in tree networks
This article investigates a network interdiction problem on a tree network: given a subset of nodes chosen as facilities, an interdictor may dissect the network by removing a size-constrained set of edges, striving to worsen the established facilities best possible. Here, we consider a reachability objective function, which is closely related to the covering objective function: the interdictor aims to minimize the number of customers that are still connected to any facility after interdiction. For the covering objective on general graphs, this problem is known to be NP-complete (Fröhlich and Ruzika In: On the hardness of covering-interdiction problems. Theor. Comput. Sci., 2021). In contrast to this, we propose a polynomial-time solution algorithm to solve the problem on trees. The algorithm is based on dynamic programming and reveals the relation of this location-interdiction problem to knapsack-type problems. However, the input data for the dynamic program must be elaborately generated and relies on the theoretical results presented in this article. As a result, trees are the first known graph class that admits a polynomial-time algorithm for edge interdiction problems in the context of facility location planning.
- 10 May 2021
- Published by Springer Nature in TOP
- Vol. 30 (1) , 95-118
Open AccessInterdicting facilities in tree networks
This article investigates a network interdiction problem on a tree network: given a subset of nodes chosen as facilities, an interdictor may dissect the network by removing a size-constrained set of edges, striving to worsen the established facilities best possible. Here, we consider a reachability objective function, which is closely related to the covering objective function: the interdictor aims to minimize the number of customers that are still connected to any facility after interdiction. For the covering objective on general graphs, this problem is known to be NP-complete (Fröhlich and Ruzika In: On the hardness of covering-interdiction problems. Theor. Comput. Sci., 2021). In contrast to this, we propose a polynomial-time solution algorithm to solve the problem on trees. The algorithm is based on dynamic programming and reveals the relation of this location-interdiction problem to knapsack-type problems. However, the input data for the dynamic program must be elaborately generated and relies on the theoretical results presented in this article. As a result, trees are the first known graph class that admits a polynomial-time algorithm for edge interdiction problems in the context of facility location planning.
- Open Access
Covering edges in networks
- 1 February 2020
- Published by Elsevier in European Journal of Operational Research
- Vol. 280 (3) , 1160-1170
Shortest paths with ordinal weights
- 1 February 2020
- Published by Elsevier in European Journal of Operational Research
- Vol. 280 (3) , 1160-1170
Shortest paths with ordinal weights
- 27 June 2019
- Published by Springer Nature
- p. 31-43
Shortest Coverage Sequences for Covering Moving Targets in Networks
- 27 June 2019
- Published by Springer Nature
- p. 31-43
Shortest Coverage Sequences for Covering Moving Targets in Networks
- 27 June 2019
- Published by Springer Nature
- p. 45-59
A Heuristic Approach for the Drone Placement Problem
- 27 June 2019
- Published by Springer Nature
- p. 45-59
A Heuristic Approach for the Drone Placement Problem