Most Vital Segment Barriers

We study continuous analogues of ``vitality'' for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a polygonal domain. This extends the graph-theoretic notion of ``most vital arcs'' for flows/paths to geometric environments. We give hardness results and efficient algorithms for various versions of the problem, (almost) completely separating hard and polynomially-solvable cases.

keywords: Computational Geometry, Graphs Theory

Conference Proceedings (peer-reviewed)

Frank Staals, Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk
Most Vital Segment Barriers
Proc. 16th Algorithms and Data Structures Symposium
495–509, 2019
https://doi.org/10.1007/978-3-030-24766-9_36

Archived Publication (not reviewed)

Frank Staals, Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk
Most Vital Segment Barriers
1905.01185, 2019
http://arXiv.org/abs/1905.01185

back to list