453
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Find all the matchings with five edges for the given sample bipartite
graph.
Use the algorithm given in the text to find maximum matchings for
random bipartite graphs with 50 vertices and 100 edges. About how many
edges are in the matchings?
Construct a bipartite graph with six nodes and eight edges which has a
three-edge matching, or prove that none exists.
Suppose that vertices in a bipartite graph represent jobs and people and
that each person is to be assigned to two jobs. Will reduction to network
flow give an algorithm for this problem? Prove your answer.
Modify the network flow program of Chapter 33 to take advantage of the
special structure of the O-l networks which arise for bipartite matching.
Write an efficient program for determining whether an assignment for the
marriage problem is stable.
Is it possible for two men to get their last choice in the stable marriage
algorithm? Prove your answer.
Construct a set of preference lists for = 4 for the stable marriage
problem where everyone gets their second choice, or prove that no such
set exists.

Muthemutik,
1 (1959).
S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1980.
D. E. Knuth, Marriages stables, Les Presses de de Montreal,
Montreal, 1976.
J. R. Kruskal Jr., “On the shortest spanning of a graph and the
traveling salesman problem,” Proceedings AMS, 7, 1 (1956).
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms
and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.
R. C. Prim, “Shortest connection networks and some generalizations,” Bell
System Technical Journal, 36 (1957).
R. E. “Depth-first search and linear graph algorithms,” SIAM Journal
on Computing, 1, 2 (1972).
J. van Leeuwen and R. E. “Worst-case analysis of set-union algo-
rithms,” Journal of the ACM, to appear.
ADVANCED TOPICS

35. Algorithm Machines
The algorithms that we have studied are, for the most part, remarkably
robust in their applicability. Most of the methods that we have seen
are a decade or more old and have survived many quite radical changes in
computer hardware and software. New hardware designs and new software
capabilities certainly can have a significant impact on specific algorithms, but
good algorithms on old machines are, for the most part, good algorithms on
new machines.
One reason for this is that the fundamental design of “conventional”
computers has changed little over the years. The design of the vast majority
of computing systems is guided by the same underlying principle, which was
developed by the mathematician J. von Neumann in the early days of modern
computing. When we speak of the von Neumann model of computation, we