A Congestion Parameter for Depth-First Graph Traversals

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen +1

We explore a new graph parameter, the KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a pr…