Name
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 et. al. [7]); (2) BPM in constant genus graphs is in NL (orthogonal to the SPL bound from Datta et. al. [8]); (3) BPM in poly-logarithmic genus graphs is in NC; (extends the NC bound for O(log n) genus graphs from Mahajan and Varadarajan [22], and Kulkarni et. al. [19]. For Part (1) we combine the flow technique of Miller and Naor [23] with the double counting technique of Reinhardt and Allender [27]. For Part (2) and (3) we extend [23] to higher genus surfaces in the spirit of Chambers, Erickson and Nayyeri [4]. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.4230/LIPIcs.STACS.2012.254 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Perfect Matching,Graphs on Surfaces,Space Complexity,NC,UL | Binary logarithm,Graph,Discrete mathematics,Combinatorics,Bipartite graph,Matching (graph theory),Planar graph,Mathematics,Parallel complexity | Conference |
Volume | ISSN | Citations |
14 | 1868-8969 | 5 |
PageRank | References | Authors |
0.42 | 24 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Arjun Gopalan | 2 | 5 | 0.42 |
| Raghav Kulkarni | 3 | 172 | 19.48 |
| Raghunath Tewari | 4 | 83 | 9.82 |