A class of fixed‐point problems on graphs and iterative solution algorithms
Tetsuo Tamai · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1993
Abstract A family of well‐known problems on graphs including the shortest‐path problem and the data flow analysis problem can be formulated as a fixed‐point problem. The lattice is used to represent the algebraic structure of information and the problem is formulated with fixed‐point equations where unknown variables that label vertices of the graph take values over the lattice. Then a practical solution algorithm based on the iterative approach that solves the unified problem is given. When applied to the shortest‐path problem, the algorithm is equivalent to the well‐known potential method but its validity for the generally formulated problem is not trivial. The correctness and termination of the algorithm within a general framework is proved. Finally, the formulation is compared to other formulations and the most fundamental structure of the problem is discussed. The relation between the general algorithm and various existing methods for each specific domain are analyzed and it is shown that for the data flow problem, the general algorithm practically is improving existing iterative methods such as Kildall's and that of Hecht and Ullman.