An optimal algorithm for the period of a strongly connected digraph

DOI10.1016/0020-0190(92)90106-6MaRDI QIDQ1209368zbMATH OpenOpenAlexFDO

Authors Adriano Pascoletti

Publication date 16 May 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(92)90106-6

zbMATH Keywords

breadth-first searchirreducible matricesperiodsingle-source shortest pathsstrongly connected digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

This paper presents a simple modification of the breadth-first search for the single-source shortest paths problem that allows the computation of the period in an optimal fashion: \(O(| E|)\) time and space. Moreover, the constants hidden by the \(O(\cdot)\) notation are small, so the proposed algorithm turns out to be very efficient on strongly connected digraphs of any size. The interest in the period --- a seemingly strange quantity --- arises from the theory of non-negative irreducible matrices and its applications, e.g. spectral and structural properties of graphs, long-term behaviour of non-negative discrete time dynamical systems, Markov chains, etc.

Recommendations

• Computing matrix period in max--min algebra
• Matrix period in max-algebra
• Maximum cycle-means of weighted digraphs
• Circuit bases of strongly connected digraphs
• Periodic dynamic graphs. Random walks problem and the shortest path

Cites work

• Cell-to-cell mapping. A method of global analysis for nonlinear systems
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster algorithms for the shortest path problem
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3532286 (Why is no real title available?)
• scientific article; zbMATH DE number 3225772 (Why is no real title available?)
• scientific article; zbMATH DE number 3236503 (Why is no real title available?)
• scientific article; zbMATH DE number 3283153 (Why is no real title available?)
• Non-negative matrices and Markov chains. 2nd ed

Cited in

(2)

• Connected components and minimum paths
• An Optimal Lower Bound for the Size of Periodic Digraphs

This page was built for publication: An optimal algorithm for the period of a strongly connected digraph

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