Discrete Algorithms Based on a Unified Method Combining Data Structures and Mathematical Programming

无论是从实用的角度，还是从理论的角度，对离散算法的研究都很活跃。近年来，人们认识到了离散算法并行化的重要意义，并行算法也得到了广泛的研究。设计高效的离散算法有两种基本方法：高效的数据结构和数学规划方法。然而，对这两个领域的研究一直是独立进行的。这使得我们有时无法开发高效的算法。人们已经认识到，为了克服这一困难，需要有一种将这两种方法相结合的方法，鉴于此，本研究的目的是寻找一种将数据结构和数学规划相结合的实用方法，并在此方法的基础上开发高效的离散算法。为了实现这一点，我们首先对在…之前开发的类似技术进行了调查对于最大流问题、最小费用流问题和最大权匹配问题的网络算法研究较多。通过这次研究，我找到了一些想法，可以开发一种将数据结构和数学规划相结合的方法来设计有效的算法，并在此方法的基础上提出新的算法。为了从理论和实践的角度对新算法进行评估，我实现了算法以及之前其他研究提出的算法，并进行了计算实验。这项研究的结果发表在IEICE《电子、通信和计算机科学基础》和《国际计算几何与应用杂志》上。其他一些论文现已提交给《计算机与系统科学杂志》和《组合理论杂志》(B)。有鉴于此，本研究的目的可以说是令人满意的。较少

Researches on discrete algorithms have been done vigorously not only from the practical point of view but also from the theoretical point of view. Recently, the significance of the parallelization of discrete algorithms has been realized and parallel algorithms have also been extensively studied. There have been two basic approaches to designing efficient discrete algorithms : efficient data structures and mathematical programming methods. However, researches on these two fields have been done independently. This prevented us from developing efficient algorithms sometimes. It has been realized that, in order to overcome this difficulty, we should have an approach which unifies these two methods.In view of the above situation, the purpose of this research is to search a useful method which unites data structures and mathematical programming and, based on the method, to develop efficient discrete algorithms. To achieve, we first made an investigation on similar techniques developped befo … More re in network algorithms for the maximum flow problem, the minimum-cost flow problem and the maximum weight matching problem. Through this investigation, I could find some idea to developping a method which unites data structures and mathematical programming to devise efficient algorithms and proposed new algorithms based on this method. To evaluate the new algorithms not only from the theoretical point of view but also from the practical point of view, I implemented the algorithms as well as the algorithms previously proposed by other researches and made computational experiments.The results in this research were published in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences and in International Journal of Computational Geometry and Applications. Some other papers are now submitted to Journal of Computer and System Sciences and Journal of Combinatorial Theory (B). In view of this, the purpose of this research can be said to be satisfatorily achieved. Less