pith. sign in

arxiv: 1905.01185 · v1 · pith:3WOX2L7Rnew · submitted 2019-05-03 · 💻 cs.CG

Most vital segment barriers

classification 💻 cs.CG
keywords barriersflowspathssegmentvitalalgorithmsalmostanalogues
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.