Research on Modeling of the Internet Problems and Efficient Algorithms

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

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.