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, Frank Staals, Valentin Polishchuk

    Proc. 2019 WADS Algorithms and Data Structures Symposium, 2019
    To Appear.
    @incollection{blocking_stick2019,
      author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                     and Polishchuk, Valentin},
      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},
      note = {To Appear.},
    }