Generalized primitivity of labeled digraphs

Gusev, Vladimir;Jungers, Raphaël;Pribavkina, Elena
(2017) Electronic Notes in Discrete Mathematics — Vol. 61, p. 549-555 (2017)

Files

1-s20-S1571065317301713-main.pdf
  • Closed Access
  • Adobe PDF
  • 198.78 KB
Request a copy

Details

Authors
  • Gusev, VladimirUCLouvain
    Author
  • Jungers, RaphaëlUCLouvain
    Author
  • Pribavkina, ElenaUral Federal University,Ekaterinburg, Russia
    Author
Abstract
We study reachability properties of digraphs whose edges are labeled by elements of a semigroup. We introduce a notion of primitivity for such digraphs, which allows us to unify a variety of recent results on the combinatorial structure of semigroups of nonnegative square matrices. We make use of Stallings foldings, a key procedure in combinatorial group theory, to design an almost-linear time algorithm for checking primitivity in an important case of allowable digraphs improving the previously known algorithm. We also present computational complexity results related to computation of the exponent.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Gusev, V., Jungers, R., & Pribavkina, E. (2017). Generalized primitivity of labeled digraphs. Electronic Notes in Discrete Mathematics, 61, 549-555. https://doi.org/10.1016/j.endm.2017.07.006 (Original work published 2017)