Most vital segment barriers

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
Place of PublicationCham
PublisherSpringer
Pages495-509
Number of pages15
ISBN (Electronic)978-3-030-24766-9
ISBN (Print)978-3-030-24765-2
DOIs
Publication statusPublished - 12 Jul 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: 5 Aug 20197 Aug 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11646 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
CountryCanada
CityEdmonton
Period5/08/197/08/19

Keywords

  • Flows and paths
  • Geodesic distance
  • Simple polygon

Fingerprint Dive into the research topics of 'Most vital segment barriers'. Together they form a unique fingerprint.

  • Cite this

    Kostitsyna, I., Löffler, M., Polishchuk, V., & Staals, F. (2019). Most vital segment barriers. In Z. Friggstad, M. R. Salavatipour, & J-R. Sack (Eds.), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings (pp. 495-509). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11646 LNCS). Springer. https://doi.org/10.1007/978-3-030-24766-9_36