Authors: Telikepalli Kavitha Kurt Mehlhorn Dimitrios Michail
Publish Date: 2009/05/20
Volume: 59, Issue: 4, Pages: 471-488
Abstract
We consider the problem of computing an approximate minimum cycle basis of an undirected nonnegative edgeweighted graph G with m edges and n vertices the extension to directed graphs is also discussed In this problem a 01 incidence vector is associated with each cycle and the vector space over mathbbF 2 generated by these vectors is the cycle space of G A set of cycles is called a cycle basis of G if it forms a basis for its cycle space A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of GCycle bases of low weight are useful in a number of contexts eg the analysis of electrical networks structural engineering chemistry and surface reconstruction Although in most such applications any cycle basis can be used a low weight cycle basis often translates to better performance and/or numerical stability Despite the fact that the problem can be solved exactly in polynomial time we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applicationsWe present two new algorithms to compute an approximate minimum cycle basis For any integer k≥1 we give 2k−1approximation algorithms with expected running time Okmn 1+2/k +mn 1+1/kω−1 and deterministic running time On 3+2/k respectively Here ω is the best exponent of matrix multiplication It is presently known that ω2376 Both algorithms are om ω for dense graphs This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θm ω boundWe also present a 2approximation algorithm with expected running time Omomegasqrtnlog n a linear time 2approximation algorithm for planar graphs and an On 3 time 242approximation algorithm for the complete Euclidean graph in the plane
Keywords: