Most vital segment barriers

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.

Corresponding Publications

Most vital segment barriers

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

Proc. 2019 WADS Algorithms and Data Structures Symposium, 2019

@incollection{blocking_stick2019,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Polishchuk, Valentin and
                 Staals, Frank},
  title = {Most vital segment barriers},
  booktitle = {Proc. 2019 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2019},
  location = {Edmonton, Alberta, Canada},
  numpages = {14},
  publisher = {Springer},
  category = {geodesic},
  doi = {10.1007/978-3-030-24766-9_36},
  url = {https://doi.org/10.1007/978-3-030-24766-9_36},
  pages = {495--509},
  editor = {Friggstad, Zachary and Sack, J{\"o}rg-R{\"u}diger
                 and Salavatipour, Mohammad R},
}