Minimum Path Bases and Relevant Paths

摘要

Given an undirected graph G(V,E) and a vertex subset U is contained in 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. Although the size distribution of subgraphs is the same in all minimum length bases, the number of cycles and paths may differ.