Zobrazeno 1 - 10
of 39
pro vyhledávání: '"Christian Wulff-Nilsen"'
Autor:
Christian Wulff-Nilsen
Publikováno v:
Journal of Computational Geometry, Vol 1, Iss 1 (2010)
Let G be a plane geometric graph where each edge is a line segment. We consider the problem of computing the maximum detour of G, defined as the maximum over all pairs of distinct points (vertices as well as interior points of edges) p and q of G of
Externí odkaz:
https://doaj.org/article/be0d1e84dcce4ae1bd033c1908adc3b6
Autor:
Panagiotis Charalampopoulos, Paweł Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen
Publikováno v:
Journal of the ACM. 70:1-50
We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial tim
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a0d3ce785d02bf3c953367b4738ebb1b
https://doi.org/10.1145/3580474
https://doi.org/10.1145/3580474
Publikováno v:
Abrahamsen, M, Holm, J, Rotenberg, E & Wulff-Nilsen, C 2020, ' Escaping an Infinitude of Lions ', American Mathematical Monthly, vol. 127, no. 10, pp. 880-896 . https://doi.org/10.1080/00029890.2020.1820837
Abrahamsen, M, Holm, J, Rotenberg, E & Wulff-nilsen, C 2020, ' Escaping an Infinitude of Lions ', The American Mathematical Monthly, vol. 127, no. 10, pp. 880-896 . https://doi.org/10.1080/00029890.2020.1820837
Abrahamsen, M, Holm, J, Rotenberg, E & Wulff-nilsen, C 2020, ' Escaping an Infinitude of Lions ', The American Mathematical Monthly, vol. 127, no. 10, pp. 880-896 . https://doi.org/10.1080/00029890.2020.1820837
We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed $1+\varepsilon$ for some value $\varepsilon>0$. Can the man survive? We answer the question in the af
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92dd038d2f4d6b6370f03d14769e8f1d
https://doi.org/10.1080/00029890.2020.1820837
https://doi.org/10.1080/00029890.2020.1820837
Publikováno v:
Bernstein, A, Nanongkai, D & Wulff-Nilsen, C 2022, Negative-Weight Single-Source Shortest Paths in Near-linear Time . in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, Annual IEEE Symposium on Foundations of Computer Science, pp. 600-611, 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Denver, Colombia, 31/10/2022 . https://doi.org/10.1109/FOCS54457.2022.00063
We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O(m\log^8(n)\log W)$ time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::28c5fc1c582c4910910f55883896fab9
Publikováno v:
SIAM Journal on Computing. 51:STOC20-i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ebf8dd59569045623cb6270e7b2475da
https://doi.org/10.1137/22n975494
https://doi.org/10.1137/22n975494
Publikováno v:
FOCS
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph $G=(V,E,w)$ undergoing edge deletions and a source vertex $r \in V$; let $n = |V|, m = |E|$ and $W$ be the aspect ratio of the graph. The goal is to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::54dc521e20cb0660cc377e4e43c58503
http://arxiv.org/abs/2004.04496
http://arxiv.org/abs/2004.04496
Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions \emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::14f6725051d8c68ae10839038b206ac6
https://doi.org/10.1137/1.9781611975994.156
https://doi.org/10.1137/1.9781611975994.156
In the decremental $(1+\epsilon)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s \in V$, and we are asked to process edge deleti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7dee5aa6ff8d42e6560bdb0142224bc6
https://doi.org/10.1137/1.9781611975994.154
https://doi.org/10.1137/1.9781611975994.154