Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

DOI10.1007/978-3-540-78773-0_63zbMath1136.68466MaRDI QIDQ5458575

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

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Cites Work

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