Algorithm for determining all finite paths in a 2D directed graph

• Autorzy: Markowski K.A. , Szlenk M. , Twardy M.

Warianty tytułu

PL

Algorytm wyznaczania dróg skończonych w dwuwymiarowym grafie skierowanym oddziaływań

• Konferencja: PELINCEC Workshop "Bridges Through Time: Intelligent Control, Signal Processing and Real-Time Process Control"
• Języki publikacji: EN

Abstrakty

EN

This paper addresses the problem of determining all finite paths in a 2D direct graph. This problem arises when one wants to compute reachability index for two-dimensional positive systems. To accomplish this task a simple algorithm has been proposed. The algorithm consists in decomposition of a 2D digraph into finite paths in which then appropriate arcs are counted. Finally, the proposed algorithm has been illustrated by a numerical example.

PL

Podano metodę wyznaczania dodatnich realizacji minimalnych dla dyskretnych układów jednowymiarowych. Sformułowano warunki wystarczające istnienia realizacji dodatnich oraz podano procedurę wyznaczania tych realizacji dla danej właściwej funkcji wymiernej. Rozważania zilustrowano przykładem numerycznym.

Słowa kluczowe

EN

2D positive system; reachability; graph theory; algorithm

PL

realizacja dodatnia; procedura; algorytm; model

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2006
• Tom: R. 82, nr 1
• Strony: 50--52
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Markowski K.A.

autor

Szlenk M.

autor

Twardy M.

• Warsaw University of Technology, Faculty of Electrical Engineering, Warsaw University of Technology, Faculty of Electronics and Information Technology,

Bibliografia

• [1] Bang-Jensen J. and Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2001
• [2] Fornasini, E. Valcher, M. E., On the positive reachability of 2D positive systems, Positive Systems, 2003, pp. 297-304, LNCIS 294
• [3] Fornasini, E. Valcher, M. E., Primitivity of positive matrix pairs: algebraic characterization, graph theoretic description and 2D system interpretation, SIAM J. Matrix Anal. Appl., 2003, pp. 71-88, vol.19, No 1
• [4] Markowski, K. Kaczorek, T., New method of determination reachability index set of 2D systems, 2005, XIII International Symposium on Theoretical Electrical Engineering ISTET 2005, Lviv
• [5] Markowski, K., Determination of the reachability subspace of the positive 2D systems described by general model using the digraph theory", 2004, VI International Workshop for Candidates for a Doctor's Degree, Wisła, (in Polish)
• [6] Ross, K. A. Wright, C. R. B., Discrete Mathematics, Prentice Hall College Div, 1992
• [7] Wilson, R. J., Introduction to Graph Theory, Addison Wesley, 1996