Maximum-Cover Source-Location Problems

Kenya SUGIHARA; Hiro ITO

doi:10.1093/ietfec/e89-a.5.1370

Maximum-Cover Source-Location Problems

Kenya SUGIHARA, Hiro ITO

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1370-1377

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1370

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Kenya SUGIHARA, Hiro ITO, "Maximum-Cover Source-Location Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1370-1377, May 2006, doi: 10.1093/ietfec/e89-a.5.1370.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1370/_p

Copy

@ARTICLE{e89-a_5_1370,
author={Kenya SUGIHARA, Hiro ITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Maximum-Cover Source-Location Problems},
year={2006},
volume={E89-A},
number={5},
pages={1370-1377},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1370},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Maximum-Cover Source-Location Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1370
EP - 1377
AU - Kenya SUGIHARA
AU - Hiro ITO
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1370
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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.
ER -