Improved Bounds for Bipartite Matching on Surfaces

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

doi:10.4230/LIPIcs.STACS.2012.254

Document

Improved Bounds for Bipartite Matching on Surfaces

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

Part of: Volume: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2012-02-24

PDF

File

PDF

LIPIcs.STACS.2012.254.pdf

Filesize: 0.59 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2012.254
URN: urn:nbn:de:0030-drops-34141

Subject Classification

Keywords

Perfect Matching
Graphs on Surfaces
Space Complexity
NC
UL

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari. Improved Bounds for Bipartite Matching on Surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 254-265, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012) https://doi.org/10.4230/LIPIcs.STACS.2012.254

Author Details

Samir Datta

Arjun Gopalan

Raghav Kulkarni

Raghunath Tewari

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail