Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

DOI10.1007/978-3-540-78773-0_63zbMATH Open1136.68466OpenAlexW1781409509MaRDI QIDQ5458575FDOQ5458575

Eva-Marta Lundell, Andrzej Lingas

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_63

Recommendations

• Efficient approximation algorithms for shortest cycles in undirected graphs
• A shortest cycle for each vertex of a graph
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Approximating the girth
• Approximating the girth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Title not available (Why is that?)
• Color-coding
• Title not available (Why is that?)
• All-Pairs Almost Shortest Paths
• Finding and counting given length cycles
• More algorithms for all-pairs shortest paths in weighted graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding a Minimum Circuit in a Graph
• Automata, Languages and Programming
• Title not available (Why is that?)
• Computing and Combinatorics
• All-pairs small-stretch paths
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• Faster Approximation of Distances in Graphs
• Packing cycles in undirected graphs
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• Approximate distance oracles
• Approximation algorithms for cycle packing problems
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Title not available (Why is that?)
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Experimental and Efficient Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• STACS 2005
• Finding even cycles even faster

Cited In (8)

• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Title not available (Why is that?)
• Approximating the Longest Cycle Problem in Sparse Graphs
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Listing all fixed-length simple cycles in sparse graphs in optimal time
• A note on finding a shortest complete cycle in an undirected graph
• Title not available (Why is that?)

This page was built for publication: Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458575)