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.最大覆盖源定位问题对于给定的图G=(V,E)，有n个顶点和m条边，并且k和p为正整数，最大覆盖源定位问题是寻找顶点子集（源）S的问题由最多 p 个顶点组成，最大化 S 覆盖的顶点数量，其中如果 S 和 v 之间的边连通性至少为 k，则顶点 v 被称为“被 S 覆盖”。这个问题有在互联网上定位镜像服务器的应用。对于这个问题，我们得到以下结果：（1）对于 k 至多 2 的 O(np+m+nlogn) 时间算法，(2) 对于 k-1 的 G 的 O(nm+n^2 logn) 时间算法边连接，(3) G 棵树的 O(knp^2) 时间算法。2。枚举孤立派从图中找到密集子图的问题与互联网搜索问题密切相关，并且最近引起了相当大的关注。然而，几乎这样的问题都很困难，例如，即使对于近似也是 NP 困难的。我们注意到，对于此类应用，我们应该找到不仅内部密集而且外部之间稀疏的子图，并且我们引入了“隔离”的概念，即，如果存在小于 ck 的子图 S，则具有 k 个顶点的子图 S 是 c 隔离的边缘 S 和 S 的外部，其中 c 称为“隔离因子”。我们提出了一种 O(c^5 2^{2c}m) 时间算法，用于枚举具有 n 个顶点和 m 个边的给定图中的所有 c 隔离子图。由此，我们直接得出，如果 c 是常数，则可以在线性时间内枚举所有 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

Single-backup-table scheme for shortest-path routing

最短路径路由的单备份表方案

• 发表时间: 2005
• 期刊: Theoretical Computer Science Vol. 333, Issue 3
• 作者: H.Ito;K.Iwama;et al.
• 通讯作者: et al.

Two equivalent measures on weighted hypergraphs

加权超图的两个等效测度

• 发表时间: 2006
• 期刊: Discrete Applied Mathematics 未定(採録決定)
• 作者: H.Ito;H.Nagamochi
• 通讯作者: H.Nagamochi

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