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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom