Development of Efficient Algorithms on Gigantic Graphs

我们开发了一些高效的算法来处理大型陈旧的图。特别是，我们的算法在一些具有一定结构的图上是有效的。我们的算法致力于解决以下三类问题。问题来自生物信息学：在生物信息学领域，我们必须处理结构简单的海量数据。二部置换图类就是这样的图类之一。提出了求解图的最大独立集和最长路的线性时间算法。具有几何表示的图：我们处理关于具有几何表示的图类的一些问题。对于某些问题，我们给出了有效的算法，对于某些问题，我们证明了这些问题很难有效地解决。例如，我们提出了一个名为“Voronoi博弈”的博弈，这是一个竞争性资源分配问题的模型。我们首先证明了这个问题在一般情况下在理论上是难解的。接下来，我们将游戏板限制为具有树结构，在这种情况下，我们将显示第一个玩家具有优势。大型网络上的问题：我们研究在给定的稠密图中寻找稀疏图的问题，使得得到的稀疏图具有期望的连通性。这个问题来自于设计一个像局域网这样的网络的实际应用。众所周知，这个问题在一般情况下在理论上是难以解决的。我们给出了该问题在一些限制图类上的逼近算法。我们还给出了算法的理论界。

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.