New Approximation Algorithms for Minimum Cycle Bases of Graphs
Lists
Only you see this
Abstract
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_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 G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k ≥ 1, we give (2k − 1)-approximation algorithms with expected running time O(k m n 1 + 2/k + m n (1 + 1/k)(ω − 1)) and deterministic running time O( n 3 + 2/k ), respectively. Here ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. Both algorithms are o( m ω ) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θ(m ω ) bound. We also present a 2-approximation algorithm with $O(m^{\omega}\sqrt{n\log n})$ expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n 3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.
BibTeX
@inproceedings{kavitha2007new,
author = {Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios Michail},
title = {{New Approximation Algorithms for Minimum Cycle Bases of Graphs}},
booktitle = {STACS},
year = {2007},
doi = {10.1007/978-3-540-70918-3\_44},
}Loading related content...