Groupe d’études et de recherche en analyse des décisions


Chopping Graphs

, , , et

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