Efficient approximation algorithms for shortest cycles in undirected graphs
From MaRDI portal
Publication:987804
DOI10.1016/j.ipl.2009.01.008zbMath1214.68466MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Unnamed Item, An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
Cites Work
- 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
- 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
