The Algorithm Design Manual Second Edition

Stop and Think: Names in Collision

Problem: “In porting code from UNIX to DOS, I have to shorten several hundred

file names down to at most 8 characters each. I can’t just use the first eight charac-

ters from each name, because “filename1” and “filename2” would be assigned the

exact same name. How can I meaningfully shorten the names while ensuring that

they do not collide?”

Solution: Construct a bipartite graph with vertices corresponding to each original

file name f

i

for 1

≤ i ≤ n, as well as a collection of acceptable shortenings for each

name f

i1

, . . . , f

ik

. Add an edge between each original and shortened name. We now

seek a set of n edges that have no vertices in common, so each file name is mapped

to a distinct acceptable substitute. Bipartite matching, discussed in Section

15.6

(page

498

), is exactly this problem of finding an independent set of edges in a

graph.

---

6 . 7

E X E R C I S E S