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

无论是从实用的角度还是从理论的角度，离散算法的研究都得到了大力的发展。近年来，人们逐渐认识到离散算法并行化的重要性，并行算法也得到了广泛的研究。设计有效的离散算法有两种基本方法：有效的数据结构和数学规划方法。然而，这两个领域的研究都是独立进行的。这有时会阻碍我们开发有效的算法。人们已经认识到，为了克服这一困难，我们应该采取一种将这两种方法结合起来的方法。鉴于上述情况，本研究的目的是寻找一种将数据结构和数学规划结合起来的有用方法，并在此基础上开发高效的离散算法。为了实现这一目标，我们首先对之前开发的类似技术进行了研究。更多的是针对最大流量问题、最小代价流问题和最大权值匹配问题的网络算法。通过这次调查，我对开发一种将数据结构和数学规划结合起来设计高效算法的方法有了一些想法，并在此方法的基础上提出了新的算法。为了从理论和实践的角度对新算法进行评估，我将这些算法以及其他研究人员之前提出的算法进行了实现，并进行了计算实验。这项研究的结果发表在IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences和International Journal of Computational Geometry and Applications上。其他论文已提交给Journal of Computer and System Sciences和Journal of Combinatorial Theory (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