120 citations
- Tel Aviv UniversityIL10 papers
- Hebrew University of JerusalemIL4 papers
- Herzliya Medical CenterIL4 papers
- University of HaifaIL4 papers
- Stanford UniversityUS3 papers
- Technion – Israel Institute of TechnologyIL3 papers
- Ariel UniversityIL2 papers
- Ben-Gurion University of the NegevIL2 papers
- Institute of Science and Technology AustriaAT2 papers
- Massachusetts Institute of TechnologyUS2 papers
- Northeastern UniversityUS2 papers
- Weizmann Institute of ScienceIL2 papers
8 papers · 1 filter
Testing Triangle Freeness in the General Model in Graphs with Arboricity
Reut Levi
We study the problem of testing triangle freeness in the general graph model. This problem was first studied in the general graph model by Alon et al. (SIAM J. Discret. Math. 2008)…
Efficient Computation of Sequence Mappability
Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka +3
In the -mappability problem, for a given sequence of length , the goal is to compute a table whose th entry is the number of indices such that the length…
Exact Distance Oracles for Planar Graphs with Failing Vertices
Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka
We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex , a target vertex and a set of fail…
Better Tradeoffs for Exact Distance Oracles in Planar Graphs
Paweł Gawrychowski, Shay Mozes, Oren Weimann +1
We present an -space distance oracle for directed planar graphs that answers distance queries in time. Our oracle both significantly simplifies and signific…
Near-Optimal Compression for the Planar Graph Metric
Amir Abboud, Pawel Gawrychowski, Shay Mozes +1
The Planar Graph Metric Compression Problem is to compactly encode the distances among nodes in a planar graph of size . Two naïve solutions are to store the graph using $O(…
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox, Philip N. Klein, Shay Mozes
Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge…