Implicit computation of maximum bipartite matchings by sublinear functional operations

作     者：Bollig, Beate Gille, Marc Proeger, Tobias 

作者机构：TU Dortmund Dortmund Germany ETH Inst Theoret Informat Zurich Switzerland 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第560卷第Part2期

页      面：131-146页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：DFG [BO 2755/1] 

主　　题：Implicit algorithms Maximum bipartite matchings Ordered binary decision diagrams 

摘      要：The maximum bipartite matching problem, an important problem in combinatorial optimization, has been studied for a long time. In order to solve problems for very large structured graphs in reasonable time and space, implicit algorithms have been investigated. Any object to be manipulated is binary encoded and problems have to be solved mainly by functional operations on the corresponding Boolean functions. OBDDs are a popular data structure for Boolean functions, therefore, OBDD-based algorithms have been used as a heuristic approach to handle large input graphs. Here, two OBDD-based maximum bipartite matching algorithms are presented, which are the first ones using only a sublinear number of operations (with respect to the number of vertices of the input graph) for a problem unknown to be in NC, the complexity class that contains all problems computable in deterministic polylogarithmic time with polynomially many processors. Furthermore, the algorithms are experimentally evaluated. (C) 2014 Elsevier B.V. All rights reserved.