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