# Computing equivalence classes among the edges of a graph with applications

F. Aurenhammer and J. Hagauer

### Abstract:

For two edges and of a connected graph let iff . Here denotes the length of a shortest path in joining vertices and . An algorithm is presented that computes the equivalence classes induced on by the transitive closure of in time and space . Finding the equivalence classes of is the primary step of several graph algorithms.

Reference: F. Aurenhammer and J. Hagauer. Computing equivalence classes among the edges of a graph with applications. Discrete Mathematics, 109:3-12, 1992. Special Issue. [IIG-Report-Series 271, TU Graz, Austria, 1989].