Development of Efficient Algorithms on Gigantic Graphs

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

We developed some efficient algorithms which work on a large stale graph. Especially, our algorithms work efficiently on some graphs which have some structures. There are three kinds of problems of which our algorithms aim to solve as follows.1. Problems come from bioinformatics': In the area of bioinformatics, we have to handle tons of data which have simple structure. The class of bipartite permutation graph is one of such graph classes. We develop linear time algorithms that solve maximum independent set and longest path on a graph in the class.2. Graphs that have geometrical representations: We deal with some problems on graph classes that have geometric representations. For some problems, we give efficient algorithms, and for some problems, we prove that the problems are hard to solve efficiently. For example, we propose a game named "Voronoi game," which is a model for competitive resource distribution problem. We first show that this problem is theoretically intractable in general case. We next restrict the game board to having a tree structure, and in that case, we show that the first player has an advantage.3. Problems on large networks: We investigate problems for finding a sparse graph in a given dense graph such that the resultant sparse graph has a desired connectivity. This problem comes from the real applications of designing a network like LAN. It is known that this problem is theoretically intractable in general case. We give some approximation algorithms for the problem on some restricted graph classes. We also give theoretical bounds of the algorithms.