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

点击翻译按钮获取中文摘要

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.