کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430727 | 688133 | 2012 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Space complexity of perfect matching in bounded genus bipartite graphs Space complexity of perfect matching in bounded genus bipartite graphs](/preview/png/430727.png)
We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the log-space complexity class Stoic Probabilistic Log-space (SPL). Since SPL is contained in the log-space counting classes ⊕L⊕L (in fact in ModkL for all k⩾2k⩾2), C=LC=L, and PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs can be performed by a log-space transducer with an SPL oracle. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a log-space computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function.
► We show that deciding whether a bipartite bounded genus graph has a perfect matching is in SPL.
► We also show that computing a perfect matching, for this class of graphs is in FLSPLFLSPL.
► We design a log-space computable and weight function to isolate the minimum weight perfect matching in such graphs.
► We also give a combinatorial embedding of such graphs in an appropriate fundamental polygon in log-space.
Journal: Journal of Computer and System Sciences - Volume 78, Issue 3, May 2012, Pages 765–779