A combinatorial algorithm for weighted stable sets in bipartite graphs |
| |
Authors: | Ulrich Faigle |
| |
Institution: | a ZAIK, Center for Applied Computer Science, University of Cologne, Cologne, Germany b Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany |
| |
Abstract: | Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford-Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs. |
| |
Keywords: | Stable set Bipartite graph Tree solution |
本文献已被 ScienceDirect 等数据库收录! |
|