TBI 01-pfs-014
Minimum Path Bases and Relevant Paths<br>
## 01-pfs-014

#
Abstract:

Minimum Path Bases and Relevant Paths

[PostScript]
[PDF]

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

Given an undirected graph *G(V,E)* and a vertex subset *U* of
*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.

Presented at the conference *Recent Trends in Graph Theory,
Algebraic Combinatorics, and Graph Algorithms*, Bled (Slovenia)
Sep 24-27 (2001).

**Keywords:**
Cycle Space, Relevant Cycles and Paths

**AMS subject classification:**
05C38 [paths and cycles]

Return to 2001 working papers list.