Development of Efficient Algorithms on Gigantic Graphs

巨图高效算法的开发

• 批准号: 18500009
• 负责人: UEHARA Ryuhei
• 金额: $ 2.65万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18500009/
• 关键词: Algorithm; Information science; Mathematical science; Bioinformatics; グラフクラス; スケールフリー; 区間グラフ

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.

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

项目成果

Linear Structure of Bipartite Permutation Graphs with anApplication

二部置换图的线性结构及其应用

• 发表时间: 2007
• 期刊: Information Processing Letters 103(2)
• 作者: R. Uehara;G. Valiente
• 通讯作者: G. Valiente

ある投票ゲームに関する戦略のモデル化

为投票游戏建立策略模型

• 发表时间: 2007
• 作者: 上原 隆平;河村 泰之;松永 博充;元木 光雄
• 通讯作者: 元木 光雄

Simple Efficient Algorithm for MPQ-tree of an Interval Graph

区间图MPQ树的简单高效算法

• 发表时间: 2007
• 期刊: KOREA-JAPAN Joint Workshop on Algorithms and Computation
• 作者: T.Saitoh;M.Kiyomi;and R.Uehara
• 通讯作者: and R.Uehara

Bandwidth of Bipartite Permutation Graphs

二部置换图的带宽

• 发表时间: 2007
• 作者: A.Brandstaedt;F.F.Dragan;H.-O.Le;V.B.Le;R.Uehara;R.Uehara
• 通讯作者: R.Uehara

Longest Path Problems on Ptolemaic Graphs

• DOI: 10.1093/ietisy/e91-d.2.170
• 发表时间: 2008-02
• 期刊: IEICE Trans. Inf. Syst.
• 作者: Y. Takahara;S. Teramoto;Ryuhei Uehara