Most vital segment barriers

I. Kostitsyna; M. Löffler; Valentin Polishchuk; F. Staals

doi:10.1007/978-3-030-24766-9_36

Most vital segment barriers

I. Kostitsyna, M. Löffler, Valentin Polishchuk, F. Staals^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Algorithms and Data Structures
Subtitle of host publication	16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings
Editors	Zachary Friggstad, Jörg-Rüdiger Sack, Mohammad R Salavatipour
Publisher	Springer
Pages	495-509
Edition	1
ISBN (Electronic)	978-3-030-24766-9
ISBN (Print)	978-3-030-24765-2
DOIs	https://doi.org/10.1007/978-3-030-24766-9_36
Publication status	Published - 13 Jul 2019

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11646
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Simple polygon
Geodesic distance
Flows and paths

Access to Document

10.1007/978-3-030-24766-9_36

Kostitsyna2019_Chapter_MostVitalSegmentBarriersFinal published version, 506 KBLicence: Taverne

Cite this

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 ed., pp. 495-509). (Lecture Notes in Computer Science ; Vol. 11646). Springer. https://doi.org/10.1007/978-3-030-24766-9_36

@inproceedings{561e408fe1c5479ab10695860a960a8b,

title = "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.",

keywords = "Simple polygon, Geodesic distance, Flows and paths",

author = "I. Kostitsyna and M. L{\"o}ffler and Valentin Polishchuk and F. Staals",

year = "2019",

month = jul,

day = "13",

doi = "10.1007/978-3-030-24766-9\_36",

language = "English",

isbn = "978-3-030-24765-2",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "495--509",

editor = "Friggstad, \{Zachary \} and J{\"o}rg-R{\"u}diger Sack and Salavatipour, \{Mohammad R \}",

booktitle = "Algorithms and Data Structures",

edition = "1",

}

Kostitsyna, I, Löffler, M, Polishchuk, V & Staals, F 2019, Most vital segment barriers. in Z Friggstad, J-R Sack & MR 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

Most vital segment barriers. / Kostitsyna, I.; Löffler, M.; Polishchuk, Valentin et al.
Algorithms and Data Structures: 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings. ed. / Zachary Friggstad; Jörg-Rüdiger Sack; Mohammad R Salavatipour. 1. ed. Springer, 2019. p. 495-509 (Lecture Notes in Computer Science ; Vol. 11646).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Most vital segment barriers

AU - Kostitsyna, I.

AU - Löffler, M.

AU - Polishchuk, Valentin

AU - Staals, F.

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - Simple polygon

KW - Geodesic distance

KW - Flows and paths

U2 - 10.1007/978-3-030-24766-9_36

DO - 10.1007/978-3-030-24766-9_36

M3 - Conference contribution

SN - 978-3-030-24765-2

T3 - Lecture Notes in Computer Science

SP - 495

EP - 509

BT - Algorithms and Data Structures

A2 - Friggstad, Zachary

A2 - Sack, Jörg-Rüdiger

A2 - Salavatipour, Mohammad R

PB - Springer

ER -

Most vital segment barriers

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this