License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.254
URN: urn:nbn:de:0030-drops-34141
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3414/
Go to the corresponding LIPIcs Volume Portal

Datta, Samir ; Gopalan, Arjun ; Kulkarni, Raghav ; Tewari, Raghunath

Improved Bounds for Bipartite Matching on Surfaces

pdf-format:
30.pdf (0.6 MB)

Abstract

We exhibit the following new upper bounds on the space complexity and the parallel complexity of the Bipartite Perfect Matching (BPM) problem for graphs of small genus:
(1) BPM in planar graphs is in UL (improves upon the SPL bound from Datta, Kulkarni, and Roy;
(2) BPM in constant genus graphs is in NL (orthogonal to the SPL bound from Datta, Kulkarni, Tewari, and Vinodchandran.;
(3) BPM in poly-logarithmic genus graphs is in NC; (extends the NC bound for O(log n) genus graphs from Mahajan and Varadarajan, and Kulkarni, Mahajan, and Varadarajan.

For Part (1) we combine the flow technique of Miller and Naor with the double counting technique of Reinhardt and Allender . For Part (2) and (3) we extend Miller and Naor's result to higher genus surfaces in the spirit of Chambers, Erickson and Nayyeri.

BibTeX - Entry

@InProceedings{datta_et_al:LIPIcs:2012:3414,
  author =	{Samir Datta and Arjun Gopalan and Raghav Kulkarni and Raghunath Tewari},
  title =	{{Improved Bounds for Bipartite Matching on Surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{254--265},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3414},
  URN =		{urn:nbn:de:0030-drops-34141},
  doi =		{10.4230/LIPIcs.STACS.2012.254},
  annote =	{Keywords: Perfect Matching, Graphs on Surfaces, Space Complexity, NC, UL  }
}

Keywords: Perfect Matching, Graphs on Surfaces, Space Complexity, NC, UL
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

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