Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

Autor:	Glencora Borradaile, Yahav Nussbaum, Christian Wulff-Nilsen, Shay Mozes, Philip N. Klein
Rok vydání:	2017
Předmět:	FOS: Computer and information sciences Discrete Mathematics (cs.DM) General Computer Science Planar straight-line graph General Mathematics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics symbols.namesake Pathwidth Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Mathematics Discrete mathematics Book embedding Nowhere-zero flow Flow network 1-planar graph Feedback arc set Longest path problem Planar graph 010201 computation theory & mathematics symbols 020201 artificial intelligence & image processing Maximal independent set Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	FOCS
ISSN:	1095-7111 0097-5397
DOI:	10.1137/15m1042929
Popis:	We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs. 18 pages, 1 figure
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b106642e8623a0f12486e41f8c5f3edd https://doi.org/10.1137/15m1042929 Zobrazit plný text záznamu