The complexity of computing the period and the exponent of a digraph

DOI10.1016/J.IPL.2025.106590MaRDI QIDQ6912025zbMATH OpenFDO

Authors Stefan Kiefer, Andrew Ryzhikov

Publication date 23 October 2025

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

Full work available at URL https://doi.org/10.1016/J.IPL.2025.106590

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Computing a graph's period quadratically by node condensation
• Counting quantifiers, successor relations, and logarithmic space
• Division in logspace-uniform NC
• Finding the Cyclic Index of an Irreducible, Nonnegative Matrix
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• Modularity of cycles and paths in graphs
• Non-negative matrices and Markov chains.
• On a sharp estimation in the theory of binary relations on a finite set
• On the index of convergence of an irreducible Boolean matrix
• Similarity of automorphisms of the torus
• The complexity of iterated multiplication
• The road coloring problem
• The Structure of Powers of Nonnegative Matrices I. The Index of Convergence
• Undirected connectivity in log-space

Cited in

(1)

• Periods of strongly connected multivariate digraphs

This page was built for publication: The complexity of computing the period and the exponent of a digraph

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