2001-05a.pmg-ley-pfs
#
Minimum Path Bases and Relevant Paths

### Abstract

Given an undirected graph *G(V,E)* and a vertex subset *U\subseteq V* the
*U*-space is the vector space over GF(2) spanned by the paths
with end-points in *U* and the cycles in *G(V,E)*. We extend Vismara's
algorithm to the computation of the union of all minimum length bases of
the *U*-space.

**Mathematics Subject Classification:**
05C38 (paths and cycles), 05C85 (graph algorithms)

**Keywords:**
graph theory, cycle space, relevant cycles and paths, minimum length basis

Download Preprint
[ PostScript | PDF ]

Josef.Leydold@statistik.wu-wien.ac.at