TY - GEN
T1 - Constant congestion routing of symmetric demands in planar directed graphs
AU - Chekuri, Chandra
AU - Ene, Alina
AU - Pilipczuk, Marcin
N1 - Funding Information:
Supported in part by NSF grant CCF-1319376. Research done while the author was at University of Warwick, partially supported by DIMAP and by Warwick-QMUL Alliance in Advances in Discrete Mathematics and its Applications.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V,E) and a collection of k source-destination pairs M = {s1t1, . . . , sktk}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair siti is routed in the symmetric setting if there is a directed path connecting si to ti and a directed path connecting ti to si. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size (h/polylog(h)).
AB - We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V,E) and a collection of k source-destination pairs M = {s1t1, . . . , sktk}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair siti is routed in the symmetric setting if there is a directed path connecting si to ti and a directed path connecting ti to si. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size (h/polylog(h)).
KW - Disjoint paths
KW - Planar directed graph
KW - Symmetric demands
UR - http://www.scopus.com/inward/record.url?scp=85012909061&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85012909061&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2016.7
DO - 10.4230/LIPIcs.ICALP.2016.7
M3 - Conference contribution
AN - SCOPUS:85012909061
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -