Efficient approximation algorithms for shortest cycles in undirected graphs

DOI10.1016/J.IPL.2009.01.008MaRDI QIDQ987804zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmgraph algorithmshortest cycleundirected graphtime complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Paths and cycles (05C38)

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 1875406 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• All-Pairs Almost Shortest Paths
• All-pairs small-stretch paths
• 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 Even Cycles Even Faster
• 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 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

(17)

• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• A note on finding a shortest complete cycle in an undirected graph
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• scientific article; zbMATH DE number 3876619 (Why is no real title available?)
• scientific article; zbMATH DE number 7561542 (Why is no real title available?)
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• scientific article; zbMATH DE number 7204576 (Why is no real title available?)
• Approximating the girth
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Listing all fixed-length simple cycles in sparse graphs in optimal time
• Fast distributed algorithms for girth, cycles and small subgraphs
• A shortest cycle for each vertex of a graph
• Approximating the Longest Cycle Problem in Sparse Graphs
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Approximating the girth
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths

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 Q987804)