An error was encountered while trying to add the item to the cart. Please try again.
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Network Flows and Matching: First DIMACS Implementation Challenge

Edited by: David S. Johnson
A co-publication of the AMS and DIMACS
Available Formats:
Hardcover ISBN: 978-0-8218-6598-9
Product Code: DIMACS/12
592 pp
List Price: $131.00 MAA Member Price:$117.90
AMS Member Price: $104.80 Electronic ISBN: 978-1-4704-3970-5 Product Code: DIMACS/12.E 592 pp List Price:$123.00
MAA Member Price: $110.70 AMS Member Price:$98.40
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $196.50 MAA Member Price:$176.85
AMS Member Price: $157.20 Click above image for expanded view Network Flows and Matching: First DIMACS Implementation Challenge Edited by: David S. Johnson A co-publication of the AMS and DIMACS Available Formats:  Hardcover ISBN: 978-0-8218-6598-9 Product Code: DIMACS/12 592 pp  List Price:$131.00 MAA Member Price: $117.90 AMS Member Price:$104.80
 Electronic ISBN: 978-1-4704-3970-5 Product Code: DIMACS/12.E 592 pp
 List Price: $123.00 MAA Member Price:$110.70 AMS Member Price: $98.40 Bundle Print and Electronic Formats and Save! This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version. List Price:$196.50
MAA Member Price: $176.85 AMS Member Price:$157.20
• Book Details

DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
Volume: 121993
MSC: Primary 68; 90;

Interest has grown recently in the application of computational and statistical tools to problems in the analysis of algorithms. In many algorithmic domains worst-case bounds are too pessimistic and tractable probabilistic models too unrealistic to provide meaningful predictions of practical algorithmic performance. Experimental approaches can provide knowledge where purely analytical methods fail and can provide insights to motivate and guide deeper analytical results. The DIMACS Implementation Challenge was organized to encourage experimental work in the area of network flows and matchings. Participants at sites in the U.S., Europe, and Japan undertook projects between November 1990 and August 1991 to test and evaluate algorithms for these problems. The Challenge culminated in a three-day workshop held in October 1991 at DIMACS. This volume contains the revised and refereed versions of twenty-two of the papers presented at the workshop, along with supplemental material about the Challenge and the Workshop.

Research mathematicians and computer scientists.

• Chapters
• Goldberg’s algorithm for maximum flow in perspective: a computational study
• Implementations of the Goldberg-Tarjan maximum flow algorithm
• Implementing a maximum flow algorithm: experiments with dynamic trees
• Implementing the push-relabel method for the maximum flow problem on a connection machine
• A case study in algorithm animation: maximum flow algorithms
• An empirical study of Min cost flow algorithms
• On implementing scaling push-relabel algorithms for the minimum-relabel algorithms for the minimum-cost flow problem
• Performance evaluation of the MINET minimum cost netflow solver
• A speculative contraction method for minimum cost flows: toward a practical algorithm
• An experimental implementation of the dual cancel and tighten algorithm for minimum-cost network flow
• A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope
• An efficient implementation of a network interior point method
• On the massively parallel solution of linear network flow problems
• Approximating concurrent flow with unit demands and capacities: an implementation
• Implementation of a combinatorial multicommodity flow algorithm
• Reverse auction algorithms for assignment problems
• An approximate dual projective algorithm for solving assignment problems
• An implementation of a shortest augmenting path algorithm for the assignment problem
• The assignment problem on parallel architectures
• An experimental comparison of two maximum cardinality matching programs
• Implementing an $O(\sqrt {N}M)$ cardinality matching algorithm
• Solving large-scale matching problems
• appendix A. Electronically available materials
• appendix B. Panel discussion highlights
• Request Review Copy
Volume: 121993
MSC: Primary 68; 90;

Interest has grown recently in the application of computational and statistical tools to problems in the analysis of algorithms. In many algorithmic domains worst-case bounds are too pessimistic and tractable probabilistic models too unrealistic to provide meaningful predictions of practical algorithmic performance. Experimental approaches can provide knowledge where purely analytical methods fail and can provide insights to motivate and guide deeper analytical results. The DIMACS Implementation Challenge was organized to encourage experimental work in the area of network flows and matchings. Participants at sites in the U.S., Europe, and Japan undertook projects between November 1990 and August 1991 to test and evaluate algorithms for these problems. The Challenge culminated in a three-day workshop held in October 1991 at DIMACS. This volume contains the revised and refereed versions of twenty-two of the papers presented at the workshop, along with supplemental material about the Challenge and the Workshop.

Research mathematicians and computer scientists.

• Chapters
• Goldberg’s algorithm for maximum flow in perspective: a computational study
• Implementations of the Goldberg-Tarjan maximum flow algorithm
• Implementing a maximum flow algorithm: experiments with dynamic trees
• Implementing the push-relabel method for the maximum flow problem on a connection machine
• A case study in algorithm animation: maximum flow algorithms
• An empirical study of Min cost flow algorithms
• On implementing scaling push-relabel algorithms for the minimum-relabel algorithms for the minimum-cost flow problem
• Performance evaluation of the MINET minimum cost netflow solver
• A speculative contraction method for minimum cost flows: toward a practical algorithm
• An experimental implementation of the dual cancel and tighten algorithm for minimum-cost network flow
• A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope
• An efficient implementation of a network interior point method
• On the massively parallel solution of linear network flow problems
• Approximating concurrent flow with unit demands and capacities: an implementation
• Implementation of a combinatorial multicommodity flow algorithm
• Reverse auction algorithms for assignment problems
• An approximate dual projective algorithm for solving assignment problems
• An implementation of a shortest augmenting path algorithm for the assignment problem
• The assignment problem on parallel architectures
• An experimental comparison of two maximum cardinality matching programs
• Implementing an $O(\sqrt {N}M)$ cardinality matching algorithm
• Solving large-scale matching problems
• appendix A. Electronically available materials
• appendix B. Panel discussion highlights
Please select which format for which you are requesting permissions.