Premium
Minimum path bases and relevant paths
Author(s) -
Gleiss Petra M.,
Leydold Josef,
Stadler Peter F.
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20080
Subject(s) - combinatorics , vertex (graph theory) , mathematics , computation , space (punctuation) , path (computing) , graph , undirected graph , distribution (mathematics) , path length , discrete mathematics , computer science , algorithm , mathematical analysis , programming language , operating system , computer network
Given an undirected graph G ( V , E ) and a vertex subset U ⊆ V the U ‐space is the vector space over G F (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. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 119–123 2005