Graphical Representations of Clutters

A clutter C on a finite set S is a family of subsets of S, none of
which contains any other.  It has been proven that every clutter can be
represented as the minpaths of a K-terminal network, i.e. the minimal
sets of non-terminals in the network that are sufficient to connect
all the terminals.  While the minpaths of a network can only represent
one clutter, a single clutter may be representable by many different
networks.  The goal of this project is to create a software tool to
convert clutters to networks and vice versa while providing an
intuitive graphical user interface for the drawing and creation of
these networks and clutters.  Since many networks can represent a
single clutter, we will also attempt to develop algorithms to find the
optimal representation of a clutter, where we define an optimal
representation to be the network with the fewest terminals that
represents the clutter.

Michael Dinitz
Advisor: Kevin Wayne