期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-13
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge 14 weight function in logarithmic space, with respect to which the minimum weight perfect matching 15 in the graph is unique, if one exists. 16 As a consequence, we obtain that deciding whether the graph has a perfect matching or not is 17 in SPL. In 1999, Reinhardt, Allender and Zhou proved that if one can construct a polynomially 18 bounded weight function for a graph in logspace such that it isolates a minimum weight perfect 19 matching in the graph, then the perfect matching problem can be solved in SPL. In this paper, we 20 give a deterministic logspace construction of such a weight function.
