3 citations · 15 across the 10 of their papers we have counts for
10 papers
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…
Min-Cost Flow Duality in Planar Networks
Haim Kaplan, Yahav Nussbaum
In this paper we study the min-cost flow problem in planar networks. We start with the min-cost flow problem and apply two transformations, one is based on geometric duality of pla…
Single Source - All Sinks Max Flows in Planar Digraphs
Jakub Łącki, Yahav Nussbaum, Piotr Sankowski +1
Let G = (V,E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t in V\{s}. We show how to solve this probl…
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…