2026-07-22T08:35:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3414 2024-03-06T10:34:11Z ddc:004 open_access

Improved Bounds for Bipartite Matching on Surfaces Datta, Samir Gopalan, Arjun Kulkarni, Raghav Tewari, Raghunath Perfect Matching Graphs on Surfaces Space Complexity NC UL 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Arjun Gopalan and Raghav Kulkarni and Raghunath Tewari 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.254 urn:nbn:de:0030-drops-34141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.254 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode