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


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.