caa a22 4500 445804904 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9313-4 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9313-4 New Approximation Algorithms for Minimum Cycle Bases of Graphs [Elektronische Daten] [Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail] 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 $\mathbb{F}_{2}$ generated by these vectors is the cycle space ofG. Aset of cycles is called a cycle basis of G if it forms a basis for its cycle space. Acycle 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. 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 applications. 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(kmn 1+2/k +mn (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 expected running time $O(m^{\omega}\sqrt{n\log n})$ , 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. Springer Science+Business Media, LLC, 2009 Cycle space nationallicence Cycle basis nationallicence Approximation algorithms nationallicence Graphs nationallicence Spanners nationallicence Fast matrix multiplication nationallicence Kavitha Telikepalli Indian Institute of Science, Bangalore, India aut Mehlhorn Kurt Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany aut Michail Dimitrios Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany aut Algorithmica Springer-Verlag 59/4(2011-04-01), 471-488 0178-4617 59:4<471 2011 59 453 https://doi.org/10.1007/s00453-009-9313-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9313-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kavitha Telikepalli Indian Institute of Science, Bangalore, India aut NATIONALLICENCE 700 1- Mehlhorn Kurt Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Michail Dimitrios Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 471-488 0178-4617 59:4<471 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer