LIP6 1998/051

• Reports
  Résolution de systèmes linéaires dans les semi-anneaux et les dioïdes
• M. Minoux
• 51 pages - 12/31/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.051.ps.gz - 106 Ko
• Contact : Michel.Minoux (at) nulllip6.fr
• Ancien Thème : ANP
Many classical algorithms for solving linear systems in usual algebra may be extended to much more general algebraic structures such as semi-rings and dioids. We present here a synthetic overview of these extensions : iterative methods such as generalized JACOBI and GAUSS-SEIDEL algorithms ; elimination methods such as generalized GAUSS-JORDAN and "Escalator" algorithms ; generalized "greedy" algorithm. As interesting special cases, we find again various well-known algorithms for solving the shortest path problem on directed graphs : the FORD-BELLMANN algorithm, FLOYD'S and DANTZIG's algorithm, and DIJKSTRA's algorithm.
• Keywords : semi-rings, dioids, linear systems
• Publisher : Emmanuelle.Encrenaz (at) nulllip6.fr