1.4.6 Matching

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A (weighted) graph G=(V,E) .

Problem: Find the largest size set of edges S \in E such that each vertex in V is incident to at most one edge of S .

Implementations

  • DIMACS Implementation Challenges (FORTRAN) (rating 9)
  • Goldberg's Network Optimization Codes (C) (rating 9)
  • BIPM -- Bipartite Matching Codes (C) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • The Stanford GraphBase (C) (rating 4)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • Discrete Optimization Methods (Pascal) (rating 3)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 3)
  • Algorithms in C++ -- Sedgewick (C++) (rating 2)

    Related Problems

  • Determinants and Permanents
  • Eulerian Cycle / Chinese Postman
  • Network Flow
  • Job Scheduling
  • Set Cover

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .