权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

High-Level Processing of Huge-Scale Networks: Challenges from Graph Decomposition Theory to Practically Efficient Algorithms

大规模网络的高级处理：从图分解理论到实用高效算法的挑战

基本信息

批准号：
24650003
负责人：
IMAI Hiroshi
金额：
$ 2.5万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Challenging Exploratory Research
财政年份：
2012
资助国家：
日本
起止时间：
2012-04-01 至 2014-03-31
项目状态：
已结题

项目摘要

For huge-scale networks such as Web link graph, social network and map road network, we aim at developing fast and high-level graph data processing based on graph minor theory and related filed, together with deriving new fundamental results in those fields. Specifically, we develop a new graph decomposition, called a core-tree decomposition, as a model for complex networks, and by making use of this model with its nice characteristics, we devise new fast algorithms for shortest-path queries and reachability queries on these huge-scale social networks. Exact exponential algorithms are also investigated to enhance the wide use of exact solutions of moderately large graphs for NP-hard intractable problems by presenting a class of tractable problems having small graph parameters which hold for large social networks. Some applications to quantum computing are also shown.

对于Web链接图、社会网络和地图道路网络等大规模网络，本文的目标是基于图子式理论和相关领域，发展快速、高层次的图数据处理，并在这些领域中得到新的基础性结果。具体来说，我们开发了一种新的图分解，称为核心树分解，作为复杂网络的模型，并利用这个模型的良好特性，我们设计了新的快速算法，这些巨大的社交网络上的最短路径查询和可达性查询。精确指数算法也被研究，以提高广泛使用的NP-难处理的问题，提出了一类易于处理的问题，具有小的图参数，适用于大型社交网络的中等大的图的精确解。还展示了量子计算的一些应用。

项目成果

期刊论文数量（43）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Representing quantum graph states by binary decision diagrams

用二元决策图表示量子图状态

DOI：
发表时间：
2014
期刊：
影响因子：
0
作者：
H. Hiraishi;H. Imai;Y. Iwata;and B. Lin
通讯作者：
and B. Lin

二分決定図を用いた量子グラフ状態の表現

使用二元决策图表示量子图状态

DOI：
发表时间：
2013
期刊：
影响因子：
0
作者：
平栗勇人;平石秀史;今井浩
通讯作者：
今井浩

Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains

DOI：
发表时间：
2011
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
0
作者：
Vorapong Suppakitpaisarn;M. Edahiro;H. Imai
通讯作者：
Vorapong Suppakitpaisarn;M. Edahiro;H. Imai

Quantum states associated with 2D periodic graph

与二维周期图相关的量子态

DOI：
发表时间：
2012
期刊：
影响因子：
0
作者：
N. Fu;Y. Hirakuri;H. Imai;and A. Motoyama
通讯作者：
and A. Motoyama

Proximity and Motion Planning on 1-Rigid Planar Periodic Graphs.

1-刚性平面周期图上的邻近和运动规划。

DOI：
10.1007/978-3-642-41905-8_6
发表时间：
2013
期刊：
Transactions on Computational Science., Vol.XX, Lecture Notes in Computer Science
影响因子：
0
作者：
Norie Fu;Akihiro Hashikura;and Hiroshi Imai
通讯作者：
and Hiroshi Imai