##
1.4.6 Matching

##
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
.