Efficient approximation algorithms for shortest cycles in undirected graphs
(2008) 8th Latin American Symposium on Theoretical Informatics (LATIN 2008) In LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science 4957. p.736746 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 O(n(3/2) root logn). Thus, in general, it yields a 2 2/3 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 2approximation 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 O(n(2) log n log M).
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1145175
 author
 Lingas, Andrzej ^{LU} and Lundell, EvaMarta ^{LU}
 organization
 publishing date
 2008
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science
 editor
 Laber, Eduardo Sany and
 volume
 4957
 pages
 736  746
 publisher
 Springer
 conference name
 8th Latin American Symposium on Theoretical Informatics (LATIN 2008)
 external identifiers

 wos:000254390900063
 scopus:43049113175
 ISSN
 16113349
 03029743
 ISBN
 9783540787723
 DOI
 10.1007/9783540787730_63
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 d2b001a293fc434396d194d9b214930a (old id 1145175)
 date added to LUP
 20080428 12:14:49
 date last changed
 20170101 05:11:54
@inproceedings{d2b001a293fc434396d194d9b214930a, 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 O(n(3/2) root logn). Thus, in general, it yields a 2 2/3 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 2approximation 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 O(n(2) log n log M).}, author = {Lingas, Andrzej and Lundell, EvaMarta}, booktitle = {LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science}, editor = {Laber, Eduardo Sany}, isbn = {9783540787723}, issn = {16113349}, language = {eng}, pages = {736746}, publisher = {Springer}, title = {Efficient approximation algorithms for shortest cycles in undirected graphs}, url = {http://dx.doi.org/10.1007/9783540787730_63}, volume = {4957}, year = {2008}, }