2002-05: The split systems generated by a connected graph

DIMACS TR: 2002-05

The split systems generated by a connected graph

Authors: Melvin F. Janowitz

ABSTRACT
The bridges of a connected graph G are shown to generate splits of G that are compatible in the sense that they generate a tree. The results are extended to generalized bridges, and the theory is applied to develop new clustering algorithms. These algorithms operate by removing at each level any bridges (or generalized bridges) from the threshold graph at that level before applying any clustering criterion.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-05.ps.gz

DIMACS Home Page