Back

G-98-03

Chopping Graphs

, , , , and

BibTeX reference

Chopping a graph G means removing one edge from each connected component of G in parallel, and repeating this until no edges remain. The required number of parallel steps is called the chopping number of G. We determine optimal chopping algorithms for complete graphs and complete binary trees. For the latter we also obtain the chopping number, which comes surprisingly close to a lower bound valid for all graphs.

, 13 pages

Research Axes

Research applications