Maximum Flow in Directed Planar Graphs with Vertex Capacities (2009)
In this paper we present an O(n log n) algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the arcs. If the source...
A simpler linear-time recognition of circular-arc graphs (2006)
Abstract. We give a linear time recognition algorithm for circular-arc graphs. Our algorithm is much simpler than the linear time recognition algorithm of McConnell [10] (which is the only linear...
Certifying algorithms for recognizing proper circulararc graphs and unit circular-arc graphs (2006)
Abstract. We give two new algorithms for recognizing proper circulararc graphs and unit circular-arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves...