Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

Andrzej LingasContact Information and Eva-Marta LundellContact Information

(1)  Department of Computer Science, Lund University, 221 00 Lund, Sweden
Abstract
We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. For an undirected graph G of unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time $\mathcal{O}(n^{\frac 3 2} \sqrt {\log n }).$ Thus, in general, it yields a $2{\frac 23}$ approximation. We study also the problem of finding a simple cycle of minimum total weight in an undirected graph with nonnegative edge weights. We present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle in an undirected graph with nonnegative integer edge weights in the range { 1,2,...,M}. This algorithm runs in time $\mathcal{O}(n^2\log n \log M).$

Contact Information Andrzej Lingas
Email: Andrzej.Lingas@cs.lth.se

Contact Information Eva-Marta Lundell
Email: Eva-Marta.Lundell@cs.lth.se
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.114 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)