Hochstrasser, B., A note on Winkler's algorithm for factoring a connected graph, Discrete Mathematics 109 (1992) 127-132. Let the connected graph G be canonically embedded into a Cartesian product fl,,, CF. We improve a method of Winkler (1987) for partitioning I in a way suitable for finding the unique prime factorization of G.
We start by defining the Cartesian product of graphs. Let Gl(V,, E,) and G2(V2, E2) be graphs. Then the Cartesian product G, x G2 has as vertices the pairs (v,, v,) with ZJ~ E V, and v2 E V,. (v,, v,) is connected by an edge to (w, , w2) in Gr X G2 just when {v,, wl} E El and v2 = w2, or when v1 = w1 and {v2, w2} E E2. A connected graph G has a canonical embedding into a product graph; Winkler [9] was the first to use this embedding in a polynomial-time Cartesianfactoring algorithm for connected graphs. We show in this paper how to improve the running time of Winkler's algorithm.
Let G(V, E) be a connected graph with IV1 = n and IEI = m, and let X, y E V be arbitrary vertices. We define d&z, y) as the number of edges in a shortest path between Y and y. It is easy to see that & is a metric on V. Define a relation 6 on E (see Djokovic [3]) as follows: if e = {x, y} E E,e' = {x',y'} E E then e Oe' iff &(x, x') + 4Ay, y') f 4;(x, y') + &(x', y).
This BP ht;on is well-defined, reflexive and symmetric. Its transitive closure @ is an equivalence relation. Let Ei, i E I, be the equivalence classes of 6. Thus,