Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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) 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
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science
editor
Laber, Eduardo Sany
volume
4957
pages
736 - 746
publisher
Springer
conference name
8th Latin American Symposium on Theoretical Informatics (LATIN 2008)
conference location
Búzios, Brazil
conference dates
2008-04-07 - 2008-04-11
external identifiers
  • wos:000254390900063
  • scopus:43049113175
ISSN
0302-9743
1611-3349
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
2016-04-01 12:30:03
date last changed
2025-01-02 20:13:26
@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         = {{0302-9743}},
  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}},
  doi          = {{10.1007/978-3-540-78773-0_63}},
  volume       = {{4957}},
  year         = {{2008}},
}