Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Shay Mozes"'
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:
Theoretical Computer Science. 918:48-59
In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph $G$ such that from the labels of any three vertices $u,v,f$ we can infer the $u$-to-$v$ distance in the graph $G\setminus \{f\}$. We show that any directed
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bfb2df4bf665265ee79af11bbc1979af
https://doi.org/10.1016/j.tcs.2022.03.020
https://doi.org/10.1016/j.tcs.2022.03.020
Publikováno v:
ACM Transactions on Algorithms. 16:1-22
The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Ʃ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2e43c089eb8baeb3c3cb230255a676cf
https://doi.org/10.1145/3381878
https://doi.org/10.1145/3381878
Publikováno v:
ACM Transactions on Algorithms. 16:1-24
We present an optimal data structure for submatrix maximum queries in n × n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem in a universe of polynomial size. This gives a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bc54d18cbabae5c05d216de00fd491dc
https://doi.org/10.1145/3381416
https://doi.org/10.1145/3381416
Publikováno v:
String Processing and Information Retrieval ISBN: 9783031206429
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c189f21e92511f1359b772425aa6b3e
https://doi.org/10.1007/978-3-031-20643-6_21
https://doi.org/10.1007/978-3-031-20643-6_21
Publikováno v:
Structural Information and Communication Complexity ISBN: 9783030795269
SIROCCO
SIROCCO
In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph G such that from the labels of any three vertices u, v, f we can infer the u-to-v distance in the graph \(G\setminus \{f\}\). We show that any directed weig
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::16d3480b72f274b61f857a29fdf80c9d
https://doi.org/10.1007/978-3-030-79527-6_18
https://doi.org/10.1007/978-3-030-79527-6_18
Publikováno v:
Theoretical Computer Science. 710:66-73
We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries ( v , c ) asking for the nearest node to node v that has color c. This is a na
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::42f9cfc9e52685b886ad4cf6410002f3
https://doi.org/10.1016/j.tcs.2017.08.021
https://doi.org/10.1016/j.tcs.2017.08.021
Publikováno v:
ACM Transactions on Algorithms. 13:1-42
We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::02079c3c9e96622e054d0fd03236ffcc
https://doi.org/10.1145/3039873
https://doi.org/10.1145/3039873
Publikováno v:
FOCS
We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b106642e8623a0f12486e41f8c5f3edd
https://doi.org/10.1137/15m1042929
https://doi.org/10.1137/15m1042929