License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.41
URN: urn:nbn:de:0030-drops-133857
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13385/
Go to the corresponding LIPIcs Volume Portal

Kumar, Nikhil

Multicommodity Flows in Planar Graphs with Demands on Faces

pdf-format:
LIPIcs-ISAAC-2020-41.pdf (0.7 MB)

Abstract

We consider the problem of multicommodity flows in planar graphs. Seymour [Seymour, 1981] showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour [Okamura and Seymour, 1981] showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.

BibTeX - Entry

@InProceedings{kumar:LIPIcs:2020:13385,
  author =	{Nikhil Kumar},
  title =	{{Multicommodity Flows in Planar Graphs with Demands on Faces}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{41:1--41:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13385},
  URN =		{urn:nbn:de:0030-drops-133857},
  doi =		{10.4230/LIPIcs.ISAAC.2020.41},
  annote =	{Keywords: Combinatorial Optimization, Multicommodity Flow, Network Design}
}

Keywords: Combinatorial Optimization, Multicommodity Flow, Network Design
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI