A shortest cycle for each vertex of a graph

DOI10.1016/J.IPL.2011.07.019MaRDI QIDQ1944201zbMATHOpenAlexFDO

Authors Raphael Yuster

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.07.019

zbMATH Keywords

graph algorithmsshortest pathgirthundirected graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• scientific article; zbMATH DE number 3876619
• Approximating the girth
• Approximating the girth

Cites work

• A note on two problems in connexion with graphs
• A quick method for finding shortest pairs of disjoint paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Approximating the girth
• Color-coding
• Disjoint paths in a network
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding Even Cycles Even Faster
• Finding a Minimum Circuit in a Graph
• Matrix multiplication via arithmetic progressions
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• More algorithms for all-pairs shortest paths in weighted graphs

Cited in

(10)

• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Detecting cycles through three fixed vertices in a graph
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Removing additive structure in 3SUM-based reductions
• Improved distance queries and cycle counting by Frobenius normal form
• scientific article; zbMATH DE number 3847427 (Why is no real title available?)
• Triangles and girth in disk graphs and transmission graphs
• A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths

This page was built for publication: A shortest cycle for each vertex of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944201)