Efficient approximation algorithms for shortest cycles in undirected graphs

Summary, in English

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).

• Författare: Andrzej Lingas; Eva-Marta Lundell
• Redaktör: Eduardo Sany Laber
• Avdelning/ar: Computer Science
• Publiceringsår: 2008
• Språk: Engelska
• Sidor: 736-746
• Publikation/Tidskrift/Serie: LATIN 2008: Theoretical Informatics / Lectures Notes in Computer Science
• Volym: 4957
• Länkar: http://dx.doi.org/10.1007/978-3-540-78773-0_63
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: 8th Latin American Symposium on Theoretical Informatics (LATIN 2008)
• Conference date: 2008-04-07 - 2008-04-11
• Conference place: Búzios, Brazil
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-540-78772-3