2001-05a.pmg-ley-pfs

# Minimum Path Bases and Relevant Paths

## Petra M. Gleiss, Josef Leydold, and Peter F. Stadler

### 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

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