caa a22 4500 44580517X CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9436-7 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9436-7 Maximum Flow in Directed Planar Graphs with Vertex Capacities [Elektronische Daten] [Haim Kaplan, Yahav Nussbaum] In this paper we present an O(nlog n) time 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 and the sink are on the same face, then our algorithm can be implemented in O(n) time. For general (not planar) graphs, vertex capacities do not make the maximum flow problem more difficult, as there is a simple reduction that eliminates vertex capacities. However, this reduction does not preserve the planarity of the graph. The essence of our algorithm is a different reduction that does preserve the planarity and can be implemented in linear time. For the special case of undirected planar graphs, an algorithm with the same time complexity was recently claimed, but we show that it has a flaw. We also apply our technique to obtain a linear-time algorithm to convert a flow to an acyclic flow, and a linear-time algorithm to find a largest set of vertex-disjoint s−t paths, in a directed planar graph. Springer Science+Business Media, LLC, 2010 Maximum flow nationallicence Planar graph nationallicence Vertex capacities nationallicence Acyclic flow nationallicence Vertex-disjoint paths nationallicence Kaplan Haim The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut Nussbaum Yahav The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut Algorithmica Springer-Verlag 61/1(2011-09-01), 174-189 0178-4617 61:1<174 2011 61 453 https://doi.org/10.1007/s00453-010-9436-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9436-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kaplan Haim The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 700 1- Nussbaum Yahav The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 174-189 0178-4617 61:1<174 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer