Development of Efficient Algorithms on Gigantic Graphs

我们开发了一些有效的算法来处理大型陈旧图。特别是，我们的算法在一些具有一定结构的图上能有效地工作。我们的算法主要解决以下三种问题：1。问题来自于生物信息学：在生物信息学领域，我们必须处理大量结构简单的数据。二部置换图类就是这样的图类之一。在类2中，我们开发了求解图上最大独立集和最长路径的线性时间算法。具有几何表示的图：我们处理具有几何表示的图类上的一些问题。对于一些问题，我们给出了有效的算法，对于一些问题，我们证明了这些问题很难有效地求解。例如，我们提出了一个名为“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.