کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10346197 698774 2013 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Push-relabel based algorithms for the maximum transversal problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Push-relabel based algorithms for the maximum transversal problem
چکیده انگلیسی
We investigate the push-relabel algorithm for solving the problem of finding a maximum cardinality matching in a bipartite graph in the context of the maximum transversal problem. We describe in detail an optimized yet easy-to-implement version of the algorithm and fine-tune its parameters. We also introduce new performance-enhancing techniques. On a wide range of real-world instances, we compare the push-relabel algorithm with state-of-the-art algorithms based on augmenting paths and pseudoflows. We conclude that a carefully tuned push-relabel algorithm is competitive with all known augmenting path-based algorithms, and superior to the pseudoflow-based ones.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1266-1275
نویسندگان
, , , ,