Most vital segment barriers
Publication date
2019-07-13
Authors
Kostitsyna, I.
Löffler, M.
Polishchuk, Valentin
Staals, F.
Editors
Friggstad, Zachary
Sack, Jörg-Rüdiger
Salavatipour, Mohammad R
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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
Simple polygon, Geodesic distance, Flows and paths, Taverne
Citation
Kostitsyna, I, Löffler, M, Polishchuk, V & Staals, F 2019, Most vital segment barriers. in Z Friggstad, J-R Sack & M R Salavatipour (eds), Algorithms and Data Structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings. 1 edn, Lecture Notes in Computer Science , vol. 11646, Springer, pp. 495-509. https://doi.org/10.1007/978-3-030-24766-9_36