A combinatorial algorithm for weighted stable sets in bipartite graphs

被引：12

作者：

Faigle, U ^{[1
]}

Frahling, G

机构：

[1] Univ Cologne, Ctr Appl Comp Sci, ZAIK, Cologne, Germany

[2] Univ Paderborn, Heinz Nixdorf Inst, Paderborn, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2006年 / 154卷 / 09期

关键词：

stable set; bipartite graph; tree solution;

D O I：

10.1016/j.dam.2005.05.037

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：1380 / 1391

页数：12

共 8 条

[1]

Ahuja R. K., 1993, NETWORK FLOWS, P409

[2] INDEPENDENCE NUMBERS OF GRAPHS - EXTENSION OF THE KOENIG-EGERVARY THEOREM [J].

DEMING, RW .

DISCRETE MATHEMATICS, 1979, 27 (01) :23-33

[3]

Even S., 1975, SIAM Journal on Computing, V4, P507, DOI 10.1137/0204043

[4] An efficient implementation of a scaling minimum-cost flow algorithm [J].

Goldberg, AV .

JOURNAL OF ALGORITHMS, 1997, 22 (01) :1-29

[5] A new-old algorithm for minimum-cut and maximum-flow in closure graphs [J].

Hochbaum, DS .

NETWORKS, 2001, 37 (04) :171-193

[6]

Karzanov A.V., 1974, Sov. Math. Doklady, V15, P434

[7]

LERCHS H, 1965, T CAN I MIN METALL, V68, P17

[8]

Plummer M.D., 1986, Matching theory

← 1 →