.

0 (hodnocen0 x )

BK

Ed. 1st

Hradec Králové : Gaudeamus, 2004

vii,176 s. : il. ; 21 cm

ISBN 80-7041-762-5 (brož.)

Obsahuje bibliografii na s. 173-176 a rejstřík

Algebra - metody optimalizační - studie

000077699

Chapter 1. Periodicity in max-min algebra 1 // 1.1. Matrices and orbits in max-min algebra 2 // 1.2. Periods of matrices and orbits 4 // 1.3. Threshold digraphs 8 // Chapter 2. Computing matrix period in max-min algebra 13 // 2.1. Matrix period 14 // 2.2. Algorithm for matrix period 16 // 2.3. Balcer-Veinott’s condensation algorithm 20 // Chapter 3. Periods of special max-min matrices 21 // 3.1. Circulant matrices 21 // 3.2. Toeplitz matrices 29 // Chapter 4. TVP-hard problems in max-min algebra 35 // 4.1. Maximum Sequence Period (MSP) problem 35 // 4.2. Computing coordinate-orbit period 39 // Chapter 5. Computing orbit period in max-min algebra 43 // 5.1. Polynomial reduction of walks 44 // 5.2. Algorithm for orbit period 52 // 5.3. Reducing computational complexity 63 // Chapter 6. Reachability of the matrix period 73 // 6.1. Matrix Period Reachability (MPR) problem 74 // 6.2. TVP-completeness of MPR 83 // 6.3. Reachability condition 90 // 6.4. Polynomially solvable cases of MPR 100 // Chapter 7. Linear periodicity in max-plus algebra 105 // 7.1. Linear matrix period 105 // 7.2. Computing linear period of an irreducible matrix 111 // 7.3. Matrix Linear Periodicity (MLP) problem 118 // Chapter 8. Computing linear matrix period 125 // 8.1. Polynomial algorithm for linear matrix period 126 // 8.2. Computing coordinate-linear period is ./VP-hard 131 // 8.3. Restricted MLP problem 133 // Chapter 9. Linear periods of special matrices 137 // 9.1. Monge matrices 138 // 9.2. Circulant matrices 151 // 9.3. Toeplitz matrices 154 // Chapter 10. Generalized periodicity 161 // 10.1. Matrix periods in distributive lattices 162 // 10.2. Generalized matrix period in max-plus algebra 166 // Index 171 // Bibliography 173