Computational Complexity of Nachtigall's Representation

Author: MolnÁrovÁ M.

Source: Optimization, Volume 52, Number 1, 2003 , pp. 93-104(12)

Publisher: Taylor and Francis Ltd

Abstract:

The matrix power sequences in max-plus algebra are studied. The power sequence of a given matrix can be represented by at most n almost linear periodic sequences as described by Nachtigall (1997), 'Powers of matrices over an extremal algebra with applications to periodic graphs' (Math. Methods of Oper. Research, 46, 87-102). A more efficient algorithm for finding such a representation in more general structure is described. The improved computational complexity is shown to be O(n⁵).

Keywords: Matrix period; Max-plus algebra

Document Type: Research article

Affiliations: 1: Department of Mathematics, Faculty of Electrical Engineering and Informatics, Technical University, ul.B. Nemcovej 32, 04200 Koice, P.O. Box D-20, Slovakiaice, P.O. Box D-20, Slovakia">

Publication date: 2003-01-01

Related content

• In this: publication
• By this: publisher
• In this Subject: Mathematics and Statistics
• By this author: MolnÁrovÁ M.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers