Shay Mozes

Theory Comput. Syst., August, 2024

Õptimal Dynamic Time Warping on Run-Length Encoded Strings.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Almost Optimal Exact Distance Oracles for Planar Graphs.

[BibT_eX]

[DOI]

J. ACM, April, 2023

Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs.

[BibT_eX]

[DOI]

Shiri Chechik

CoRR, 2023

Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings.

[BibT_eX]

[DOI]

CoRR, 2023

What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

On the Hardness of Computing the Edit Distance of Shallow Trees.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2022

Improved Compression of the Okamura-Seymour Metric.

[BibT_eX]

[DOI]

Nathan Wallheimer

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

The Fine-Grained Complexity of Episode Matching.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

A Conditional Lower Bound for Episode Matching.

[BibT_eX]

[DOI]

CoRR, 2021

A Note on Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities.

[BibT_eX]

[DOI]

Dor Mesica

CoRR, 2021

A Note on a Recent Algorithm for Minimum Cut.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Planar Negative k-Cycle.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Fault-Tolerant Distance Labeling for Planar Graphs.

[BibT_eX]

[DOI]

Aviv Bar-Natan

Proceedings of the Structural Information and Communication Complexity, 2021

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs.

[BibT_eX]

[DOI]

Viktor Fredslund-Hansen

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

An Almost Optimal Edit Distance Oracle.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Compressed range minimum queries.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Minimum Cut in O(m log² n) Time.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Dynamic String Alignment.

[BibT_eX]

[DOI]

Tomasz Kociumaka

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

2019

Minimum Cut in O(m log2n) Time.

[BibT_eX]

[DOI]

CoRR, 2019

Almost optimal distance oracles for planar graphs.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Exact Distance Oracles for Planar Graphs with Failing Vertices.

[BibT_eX]

[DOI]

Benjamin Tebeka

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Faster shortest paths in dense distance graphs, with applications.

[BibT_eX]

[DOI]

Yahav Nussbaum

Theor. Comput. Sci., 2018

Compressed Range Minimum Queries.

[BibT_eX]

[DOI]

Seungbum Jo

Proceedings of the String Processing and Information Retrieval, 2018

Minimum Cut of Directed Planar Graphs in O(n log log n) Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Compression for the Planar Graph Metric.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Distance Emulator for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Efficient Approximate Distance Oracles for Vertex-Labeled Planar Graphs.

[BibT_eX]

[DOI]

Itay Laish

CoRR, 2017

Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs.

[BibT_eX]

[DOI]

Itay Laish

Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

Dispersion on Trees.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Recursive Separator Decompositions for Planar Graphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

The Nearest Colored Node in a Tree.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

Minimum Cut of Directed Planar Graphs in O(nloglogn) Time.

[BibT_eX]

[DOI]

CoRR, 2015

Efficient Vertex-Label Distance Oracles for Planar Graphs.

[BibT_eX]

[DOI]

Eyal E. Skop

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection.

[BibT_eX]

[DOI]

Kyle Fox

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Improved Submatrix Maximum Queries in Monge Matrices.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs.

[BibT_eX]

[DOI]

PhD thesis, 2013

Improved Submatrix Maximum Queries in Monge Matrices.

[BibT_eX]

[DOI]

CoRR, 2013

Structured recursive separator decompositions for planar graphs in linear time.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Short and Simple Cycle Separators in Planar Graphs.

[BibT_eX]

[DOI]

Eli Fox-Epstein

Phitchaya Mangpo Phothilimthana

Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, 2013

2012

Exact distance oracles for planar graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in $O(n^{1.5} \log n)$ Time

[BibT_eX]

[DOI]

CoRR, 2010

Exact Shortest Path Queries for Planar Graphs Using Linear Space

[BibT_eX]

[DOI]

CoRR, 2010

Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time

[BibT_eX]

[DOI]

CoRR, 2010

The Train Delivery Problem - Vehicle Routing Meets Bin Packing.

[BibT_eX]

[DOI]

Aparna Das

Claire Mathieu

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Shortest Paths in Planar Graphs with Real Lengths in O(nlog2n/loglogn) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

Shortest Paths in Planar Graphs with Real Lengths in $O(n\log^2n/\log\log n)$ Time

[BibT_eX]

[DOI]

CoRR, 2009

Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.

[BibT_eX]

[DOI]

Algorithmica, 2009

Efficient Algorithms for Analyzing Segmental Duplications, Deletions, and Inversions in Genomes.

[BibT_eX]

[DOI]

Crystal L. Kahn

Benjamin J. Raphael

Proceedings of the Algorithms in Bioinformatics, 9th International Workshop, 2009

Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Finding an optimal tree searching strategy in linear time.

[BibT_eX]

[DOI]

Krzysztof Onak

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Fast Algorithms for Computing Tree LCS.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007

An Optimal Decomposition Algorithm for Tree Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.

[BibT_eX]

[DOI]