A combinatorial algorithm for weighted stable sets in bipartite graphs
U. Faigle, G. Frahling, Discrete Applied Mathematics (2006) 1380–1391.
Download
No fulltext has been uploaded.
Journal Article
| Published
| English
Author
Faigle, Ulrich;
Frahling, Gereon
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.
Publishing Year
Journal Title
Discrete Applied Mathematics
Page
1380-1391
ISSN
LibreCat-ID
Cite this
Faigle U, Frahling G. A combinatorial algorithm for weighted stable sets in bipartite graphs. Discrete Applied Mathematics. 2006:1380-1391. doi:10.1016/j.dam.2005.05.037
Faigle, U., & Frahling, G. (2006). A combinatorial algorithm for weighted stable sets in bipartite graphs. Discrete Applied Mathematics, 1380–1391. https://doi.org/10.1016/j.dam.2005.05.037
@article{Faigle_Frahling_2006, title={A combinatorial algorithm for weighted stable sets in bipartite graphs}, DOI={10.1016/j.dam.2005.05.037}, journal={Discrete Applied Mathematics}, author={Faigle, Ulrich and Frahling, Gereon}, year={2006}, pages={1380–1391} }
Faigle, Ulrich, and Gereon Frahling. “A Combinatorial Algorithm for Weighted Stable Sets in Bipartite Graphs.” Discrete Applied Mathematics, 2006, 1380–91. https://doi.org/10.1016/j.dam.2005.05.037.
U. Faigle and G. Frahling, “A combinatorial algorithm for weighted stable sets in bipartite graphs,” Discrete Applied Mathematics, pp. 1380–1391, 2006.
Faigle, Ulrich, and Gereon Frahling. “A Combinatorial Algorithm for Weighted Stable Sets in Bipartite Graphs.” Discrete Applied Mathematics, 2006, pp. 1380–91, doi:10.1016/j.dam.2005.05.037.
Google Scholar