A shortest cycle for each vertex of a graph

DOI10.1016/j.ipl.2011.07.019zbMath1260.05083OpenAlexW2071406157MaRDI QIDQ1944201

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

shortest pathgirthgraph algorithmsundirected graph

Mathematics Subject Classification ID

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

Related Items (5)

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 ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Unnamed Item ⋮ Improved distance queries and cycle counting by Frobenius normal form

Cites Work

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

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