Efficient approximation algorithms for shortest cycles in undirected graphs

DOI10.1016/J.IPL.2009.01.008zbMATH Open1214.68466OpenAlexW2025590553MaRDI QIDQ987804FDOQ987804

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

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

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)

Cites Work

• Title not available (Why is that?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Color-coding
• All-Pairs Almost Shortest Paths
• Title not available (Why is that?)
• Finding and counting given length cycles
• More algorithms for all-pairs shortest paths in weighted graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding a Minimum Circuit in a Graph
• Automata, Languages and Programming
• Title not available (Why is that?)
• Computing and Combinatorics
• All-pairs small-stretch paths
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• Faster Approximation of Distances in Graphs
• Packing cycles in undirected graphs
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• Approximation algorithms for cycle packing problems
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Title not available (Why is that?)
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding Even Cycles Even Faster
• Experimental and Efficient Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• STACS 2005

Cited In (13)

• Title not available (Why is that?)
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Title not available (Why is that?)
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Title not available (Why is that?)
• Fast distributed algorithms for girth, cycles and small subgraphs
• Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
• Approximating the Longest Cycle Problem in Sparse Graphs
• 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
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• Title not available (Why is that?)

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)