Graphs, dioids and semirings. New models and algorithms. (Q2455350): Difference between revisions

The origins of Graph Theory date back to Euler (1736) with the solution of the celebrated `Königsberg Bridges Problem'; and to Hamilton with the famous `Trip around the World' game (1859), stating for the first time a problem which, in its most recent version -- the `Traveling Salesman Problem' --, is still the subject of active research. Yet, it has been during the last fifty years or so -- with the rise of the electronic computers -- that Graph Theory has become an indispensable discipline in terms of the number and importance of its applications across the Applied Sciences. Graph Theory has been especially central to Theoretical and Algorithmic Computer Science, and Automatic Control, Systems Optimization, Economy and Operations Research, Data Analysis in the Engineering Sciences. Close connections between graphs and algebraic structures have been widely used in the analysis and implementation of efficient algorithms for many problems, for example: transportation network optimization, telecommunication network optimization and planning, optimization in scheduling and production systems, etc. The primary objectives of the book (Graphs, dioids and semirings. New models and algorithms) are to emphasize the deep relations existing between the semiring and dioid structures with graphs and their combinatorial properties, while demonstrating the modeling and problem-solving capability and flexibility of these structures. In addition the book provides an extensive overview of the mathematical properties employed by ``nonclassical'' algebraic structures, which either extend usual algebra (i.e., semirings), or correspond to a new branch of algebra (i.e., dioids), apart from the classical structures of groups, rings, and fields. A dioid is a commutative semiring with identity for which the preorder introduced with the additive operation is an order relation. In this case, the semiring cannot be a ring. The authors build the algebra of dioids, considering the associated dioids of square matrices and that of polynomials. Some very interesting examples are deeply studied: the dioid of real numbers with Min and addition as operations, the dioid of real numbers with Max and Min as binary compositions, the dioid of the closed interval \([0,1]\) with Max and Min. Linear systems on dioids are studied also in details and are applied to graphs. The notions of determinant and characteristic polynomial of a linear operator, i.e., of a matrix, are replaced with bideterminant and characteristic bipolynomial. The book is well written and a lot of applications are given everywhere.