Research on Modeling of the Internet Problems and Efficient Algorithms

互联网问题建模及高效算法研究

• 批准号: 16500010
• 负责人: ITO Hiro
• 金额: $ 2.3万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500010/
• 关键词: graphs; networks; connectivity; enumeration; cliques; the Internet; location problems; communities; 多項式時間アルゴリズム; 孤立; 連結度増大問題; 領域グラフ; 枝連結度; 多項式時問アルゴリズム; H-彩色問題; 階層構造; NP完全; ルーチング

1. Maximum-Cover Source Location ProblemsFor a given graph G=(V,E) with n vertices and m edges and positive integers k and p, the maximum-cover source location problem is a problem of finding a vertex subsets (sources) S consisting of at most p vertices maximizing the number of covered vertices by S, where a vertex v is called "covered by S" if the edge-connectivity between S and v is at least k. This problem has applications of locating mirror servers on the Internet. For this problem we obtain the following results : (1) an O(np+m+nlogn) time algorithm for k at most 2, (2) an O(nm+n^2 logn) time algorithm for G of k-1 edge connected, (3) an O(knp^2) time algorithm for G of trees.2. Enumerating Isolated CliquesProblem of finding dense subgraphs from a graph has a close relation to the Internet search problems and recently attracts considerable attention. However, almost such problems are hard, e.g., NP-hard even for approximation. We pay attention to that for such applications we should find subgraphs not only dense inside but also sparse between outside, and we introduce an idea of "isolation," i.e., a subgraph S with k vertices is c-isolated if there exists less than ck edges S and the outside of S, where c is called an "isolation factor." We presented an O(c^5 2^{2c}m) time algorithm for enumerating all c-isolated subgraphs from a given graph with n vertices and m edges. From this, we directly obtain that we can enumerate all c-isolated graphs in lenear time if c is a constant, and polynomial time if c=O(logn). We also show that these bounds are tight.

1.最大覆盖源定位问题对于给定的n点m边正整数k和p的图G=（V，E），最大覆盖源定位问题是寻找一个最多由p个顶点组成的顶点子集（源）S，使S覆盖的顶点数最大化的问题，其中顶点v称为“被S覆盖”，如果S和v之间的边连通度至少为k。这个问题有在互联网上定位镜像服务器的应用。对于这个问题，我们得到了如下结果：（1）对于k ≤ 2，时间复杂度为O（np+m+nlogn）;（2）对于k-1边连通的G，时间复杂度为O（nm+n^2 logn）;（3）对于树的G，时间复杂度为O（knp^2）.从图中寻找稠密子图的问题与Internet搜索问题有着密切的联系，近年来引起了人们的广泛关注。然而，几乎这样的问题是困难的，例如，NP-hard，即使是近似。我们注意到，对于这样的应用，我们应该找到不仅内部密集而且外部稀疏的子图，并且我们引入了“隔离”的思想，即，一个有k个顶点的子图S是c-孤立的，如果存在少于ck条边S和S的外部，其中c被称为“孤立因子”。“我们提出了一个O（c^5 2^{2c}m）时间算法，用于从一个给定的具有n个顶点和m条边的图中枚举所有c-孤立子图。由此我们直接得到：当c为常数时，我们可以在lenear时间内枚举出所有的c-孤立图;当c=O（logn）时，我们可以在多项式时间内枚举出所有的c-孤立图。我们还表明，这些边界是紧的。

项目成果

Harary's generalized ticktacktoe

哈拉里的广义井字棋

• 发表时间: 2006
• 期刊: IEICE Transactions(in Japanese, to appear) Vol.J88-A, No.6
• 作者: Naoyasu Ubayashi;Tetsuo Tamai;H.Ito
• 通讯作者: H.Ito

NA-Edge-Connectivity Augmentation Problems by Adding Edges

通过添加边缘来增强 NA 边缘连通性问题

• 发表时间: 2004
• 期刊: Journal of the Operations Research Society of Japan Vol.47, No.4
• 作者: H.Miwa;H.Ito
• 通讯作者: H.Ito

Efficient methods of determining DNA probe sequence

确定 DNA 探针序列的有效方法

• 发表时间: 2006
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A(採録決定)
• 作者: Hiro Ito;Kazuo Iwama;Takeyuki Tamura
• 通讯作者: Takeyuki Tamura

Compact Routing with Stretch Factor of Less Than Three

拉伸因子小于 3 的紧凑布线

• 发表时间: 2005
• 期刊: IEICE transactions on Information and Systems Vol.E88-D, No.1
• 作者: K.Iwama;A.Kawachi
• 通讯作者: A.Kawachi

Three equivalent partial orders on graphs with real edge-weights drawn on a convex polygon

在凸多边形上绘制实边权重的图上的三个等效偏序

• 发表时间: 2005
• 期刊: Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG2004), LNCS 3742
• 作者: Y.Suzuki;K.Kaneko;M.Nakamori;H.Ito
• 通讯作者: H.Ito