Title: Algorithms for computing minimum cycle basis in graphs
Speaker: Prof. Kavitha Telikepalli
Affiliation: IISc. Bangalore
Date: February 24, 2009
Abstract:
Given a graph G with non-negative edge weights, a minimum cycle basis of G is a set of cycles C1,...,Ck such that every cycle in G can be written as a linear combination of C1,...,Ck and this is a minimum weight set of cycles which forms a spanning set. When G is directed, the underlying field is Q and when G is undirected, the underlying field is Z_2.
We first outline a simple greedy strategy for the problem of computing a minimum cycle basis and this yields a reasonably efficient algorithm in undirected graphs. However, for directed graphs, the intermediate numbers involved in the arithmetic get very large. We show two approaches to solve this problem: the first approach is to choose a small prime p and work over the field Z_p and the second