Advanced

Efficient approximation algorithms for shortest cycles in undirected graphs

Lingas, Andrzej LU and Lundell, Eva-Marta LU (2008) 8th Latin American Symposium on Theoretical Informatics (LATIN 2008) In LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science 4957. p.736-746
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 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 O(n(2) log n log M).
Please use this url to cite or link to this publication:
author
organization
publishing date
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
1611-3349
0302-9743
ISBN
978-3-540-78772-3
DOI
10.1007/978-3-540-78773-0_63
project
VR 2005-4085
language
English
LU publication?
yes
id
d2b001a2-93fc-4343-96d1-94d9b214930a (old id 1145175)
date added to LUP
2008-04-28 12:14:49
date last changed
2017-01-01 05:11:54
@inproceedings{d2b001a2-93fc-4343-96d1-94d9b214930a,
  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 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 O(n(2) log n log M).},
  author       = {Lingas, Andrzej and Lundell, Eva-Marta},
  booktitle    = {LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science},
  editor       = {Laber, Eduardo Sany},
  isbn         = {978-3-540-78772-3},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {736--746},
  publisher    = {Springer},
  title        = {Efficient approximation algorithms for shortest cycles in undirected graphs},
  url          = {http://dx.doi.org/10.1007/978-3-540-78773-0_63},
  volume       = {4957},
  year         = {2008},
}