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

点击翻译按钮获取中文摘要

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