Efficient approximation algorithms for shortest cycles in undirected graphs
From MaRDI portal
Publication:987804
DOI10.1016/j.ipl.2009.01.008zbMath1214.68466OpenAlexW2025590553MaRDI QIDQ987804
Andrzej Lingas, Eva-Marta Lundell
Publication date: 16 August 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.008
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Unnamed Item
Cites Work
- Finding and counting given length cycles
- All-Pairs Small-Stretch Paths
- Finding a maximum weight triangle in n 3-Δ time, with applications
- 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)
- Finding Even Cycles Even Faster
- Color-coding
- Packing cycles in undirected graphs
- Computing and Combinatorics
- All-Pairs Almost Shortest Paths
- Automata, Languages and Programming
- Experimental and Efficient Algorithms
- STACS 2005
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient approximation algorithms for shortest cycles in undirected graphs
