New Approximation Algorithms for Minimum Cycle Bases of Graphs |
| |
Authors: | Telikepalli Kavitha Kurt Mehlhorn Dimitrios Michail |
| |
Affiliation: | 1.Indian Institute of Science,Bangalore,India;2.Max-Planck-Institut für Informatik,Saarbrücken,Germany |
| |
Abstract: | We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative 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
\mathbbF2\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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|