Research Catalog

Title

Network flows and matching : first DIMACS implementation challenge / David S. Johnson, Catherine C. McGeoch, editors.

Publication

Providence, R.I. : American Mathematical Society, [1993], ©1993.

Items in the Library & Off-site

Details

Additional Authors

• Johnson, David S., 1945-
• McGeoch, Catherine C., 1959-
• DIMACS (Group)
• Challenge Workshop (1991 : DIMACS Center)

Description

xiv, 592 pages : illustrations; 27 cm.

Series Statement

DIMACS series in discrete mathematics and theoretical computer science ; v. 12

Uniform Title

DIMACS series in discrete mathematics and theoretical computer science ; v. 12.

Subjects

• Computer science > Mathematics
• System theory

Note

• "NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science, a consortium of Rutgers University, Princeton University, AT&T Bell Labs, Bellcore."
• Based on papers presented at the Challenge Workshop, held at DIMACS, Oct. 14-16, 1991.

Bibliography (note)

• Includes bibliographical references.

Contents

• Preface / D. S. Johnson and C. C. McGeoch -- Goldberg's Algorithrn for Maximum Flow in Perspective: A Computational Study / R. J. Anderson and J. C. Setubal -- Implementations of the Goldberg-Tarjan Maximum Flow Algorithm / Q. C. Nguyen and V. Venkateswaran -- Implementing a Maximum Flow Algorithm: Experiments with Dynamic Trees / T. Badics and E. Boros -- Implementing the Push-Relabel Method for the Maximum Flow Problem on a Connection Machine / F. Alizadeh and A. V. Goldberg -- A Case Study in Algorithm Animation: Maximum Flow Algorithms / G. E. Shannon, J. MacCuish and E. Johnson -- An Empirical Study of Min Cost Flow Algorithms / R. G. Bland, J. Cheriyan, D. L. Jensen and L. Ladanyi -- On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem / A. V. Goldberg and M. Kharitanov -- Performance Evaluation of the MINET Minimum Cost Netflow Solver / I. Maros --
• A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm / S. Fujishige, K. Iwano, J. Nakano and S. Tezuka -- An Experimental Implementation of the Dual Cancel and Tighten Algorithm for Minimum-Cost Network Flow / S. T. McCormick and L. Liu -- A Fast Implementation of a Path-Following Algorithm for Maximizing a Linear Function over a Network Polytope / A. Joshi, A. S. Goldstein and P. M. Vaidya -- An Efficient Implementation of a Network Interior Point Method / M. G. C. Resende and G. Veiga -- On the Massively Parallel Solution of Linear Network Flow Problems / S. Neilsen and S. Zenios -- Approximating Concurrent Flow with Unit Demands and Capacities: An Implementation / J. M. Borger, T. S. Kang and P. N. Klein -- Implementation of a Combinatorial Multicommodity Flow Algorithm / T. Leong, P. W. Shor and C. Stein -- Reverse Auction Algorithms for Assignment Problems / D. A. Castanon --
• An Approximate Dual Projective Algorithm for Solving Assigument Problems / K. G. Ramakrishnan, N. K. Karmarkar and A. P. Kamath -- An Implementation of a Shortest Augmenting Path Algorithm for the Assignment Problem / J. Hao and G. Kocur -- The Assignment Problem on Parallel Architectures / M. Brady, K. K. Jung, H. T. Nguyen, R. Raghavan and R. Subramonian -- An Experimental Comparison of Two Maximum Cardinality Matching Programs / S. T. Crocker -- Implementing an [actual symbol not reproducible] Cardinality Matching Algorithm / R. B. Mattingly and N. P. Ritchey -- Solving Large-Scale Matching Problems / D. Applegate and W. Cook -- Appendix A: Electronically Available Materials / C. C. McGeoch -- Appendix B: Panel Discussion Highlights / D. S. Johnson.

ISBN

0821865986 (acid-free)

LCCN

93028698

OCLC

• 28587304
• ocm28587304

Owning Institutions

Columbia University Libraries