Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

DOI10.1007/978-3-540-78773-0_63MaRDI QIDQ5458575zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(14)

• Short cycles via low-diameter decompositions
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• scientific article; zbMATH DE number 7204576 (Why is no real title available?)
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Approximating the girth
• Approximating the girth
• Approximating the Longest Cycle Problem in Sparse Graphs
• A shortest cycle for each vertex of a graph
• 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
• scientific article; zbMATH DE number 3876619 (Why is no real title available?)

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)