3 citations · 15 across the 10 of their papers we have counts for
5 papers · 1 filter
Minimum Cut of Directed Planar Graphs in O(nloglogn) Time
Shay Mozes, Cyril Nikolaev, Yahav Nussbaum +1
We give an time algorithm for computing the minimum cut (or equivalently, the shortest cycle) of a weighted directed planar graph. This improves the previous fas…
Faster Shortest Paths in Dense Distance Graphs, with Applications
Shay Mozes, Yahav Nussbaum, Oren Weimann
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein,…
Linear-Time Recognition of Probe Interval Graphs
Ross M. McConnell, Yahav Nussbaum
The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a varia…
Isomorphism of graph classes related to the circular-ones property
Andrew R. Curtis, Min Chih Lin, Ross M. McConnell +4
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithm…
Improved distance queries in planar graphs
Yahav Nussbaum
There are several known data structures that answer distance queries between two arbitrary vertices in a planar graph. The tradeoff is among preprocessing time, storage space and q…