Efficient parallel algorithms for r-dominating set and p-center problems on trees

Xin He; Yaacov Yesha

doi:10.1007/BF01840381

Efficient parallel algorithms for r-dominating set and p-center problems on trees

Xin He
, Yaacov Yesha

Department of Computer Science and Engineering

Ohio State University

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

We develop efficient parallel algorithms for the r-dominating set and the p-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for the r-dominating set problem runs in O(log n log log n) time with n processors. The algorithm for the p-center problem runs in O(log² n log log n) time with n processors.

Original language	English
Pages (from-to)	129-145
Number of pages	17
Journal	Algorithmica
Volume	5
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01840381
State	Published - Jun 1990

Keywords

Optimization problems
p-Center
Parallel algorithms
r-Dominating set
Trees

Access to Document

10.1007/BF01840381

Cite this

@article{8ca892695ffc4f3aa77e4e03c3f0221a,

title = "Efficient parallel algorithms for r-dominating set and p-center problems on trees",

abstract = "We develop efficient parallel algorithms for the r-dominating set and the p-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for the r-dominating set problem runs in O(log n log log n) time with n processors. The algorithm for the p-center problem runs in O(log2 n log log n) time with n processors.",

keywords = "Optimization problems, p-Center, Parallel algorithms, r-Dominating set, Trees",

author = "Xin He and Yaacov Yesha",

year = "1990",

month = jun,

doi = "10.1007/BF01840381",

language = "English",

volume = "5",

pages = "129--145",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - Efficient parallel algorithms for r-dominating set and p-center problems on trees

AU - He, Xin

AU - Yesha, Yaacov

PY - 1990/6

Y1 - 1990/6

N2 - We develop efficient parallel algorithms for the r-dominating set and the p-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for the r-dominating set problem runs in O(log n log log n) time with n processors. The algorithm for the p-center problem runs in O(log2 n log log n) time with n processors.

AB - We develop efficient parallel algorithms for the r-dominating set and the p-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for the r-dominating set problem runs in O(log n log log n) time with n processors. The algorithm for the p-center problem runs in O(log2 n log log n) time with n processors.

KW - Optimization problems

KW - p-Center

KW - Parallel algorithms

KW - r-Dominating set

KW - Trees

UR - https://www.scopus.com/pages/publications/0025206953

U2 - 10.1007/BF01840381

DO - 10.1007/BF01840381

M3 - Article

AN - SCOPUS:0025206953

SN - 0178-4617

VL - 5

SP - 129

EP - 145

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

Efficient parallel algorithms for r-dominating set and p-center problems on trees

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this