ECCC-Report TR10-201https://eccc.weizmann.ac.il/report/2010/201Comments and Revisions published for TR10-201en-usWed, 05 Jan 2011 11:16:25 +0200
Revision 1
| Perfect Matching in Bipartite Planar Graphs is in UL |
Samir Datta,
Raghav Kulkarni,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2010/201#revision1We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.Wed, 05 Jan 2011 11:16:25 +0200https://eccc.weizmann.ac.il/report/2010/201#revision1
Paper TR10-201
| Perfect Matching in Bipartite Planar Graphs is in UL |
Samir Datta,
Raghav Kulkarni,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2010/201We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.Sun, 26 Dec 2010 17:56:12 +0200https://eccc.weizmann.ac.il/report/2010/201