Zobrazeno 1 - 10
of 149
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
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
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
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
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
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
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