抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Challenging Exploratory Research, Fund Type: -, Overall Grant Amount: - (direct: 2800000, indirect: 840000)
The object of this project is establishing fundamental techniques for the “Sublinear-Time Paradigm.” The most remarkable result in this project is presenting a universal algorithm to complex networks, e.g., web graphs and social networks. That is, we define a class of (infinite) multigraphs, named HSF (Hierarchical Scale Free), which models a kind of hierarchical complex networks and prove that every property is constant-time testable for HSF. This is the first nontrivial universal constant-time algorithm on a graph class of sparse and degree-unbounded graphs, what is called the general graphs.