Re: shortest cycle between two given nodes

tchow_at_lsa.umich.edu
Date: 02/21/05 

Date: 21 Feb 2005 13:15:01 -0500

In article <cvd36e$8il$1@dizzy.math.ohio-state.edu>,
Mateus Oliveira <mateus.oliveira@gmail.com> wrote:
>Given an undirected and unweighted graph, and two of its nodes s and t,
>find the size of the shortest cycle involving s and t, or return +oo
>(or any arbitrary fixed value) if none exists. By a cycle involving
>s and t, we mean a cycle (x0,x1,...,xk-1,x0) such that there exists
>i and j for wich xi=s and xj=t.

Your cycle is equivalent to a shortest pair of vertex-disjoint paths
between s and t. See J. W. Suurballe and R. E. Tarjan, "A quick method
for finding shortest pairs of disjoint paths," Networks 14 (1984),
no. 2, 325-336. 

-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences