For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Maximum-Cover Source-Location ProblemsKenya SUGIHARA  Hiro ITO  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.5   pp.1370-1377Publication Date: 2006/05/01Online ISSN: 1745-1337 DOI: 10.1093/ietfec/e89-a.5.1370Print ISSN: 0916-8508Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)Category: Keyword: graph,  edge-connectivity,  location problem,  polynomial-time algorithm,  NP-hard,  Full Text: PDF>> Buy this Article Summary:  Given a graph G=(V,E), a set of vertices S ⊆ V covers v ∈ V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + nlog n)-time algorithm for k=2, where n=|V| and m=|E|. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k-1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.