Parallel algorithms for finding the center of interval and circular-arc graphs

被引：0

作者：

Hsu, FR ^{[1
]}

Shan, MK

机构：

[1] Taichung Healthcare & Management Univ, Dept Informat Technol, Taichung, Taiwan

[2] Natl Chengchi Univ, Dept Comp Sci, Taipei 11623, Taiwan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2003年 / E86A卷 / 10期

关键词：

parallel algorithms; EREW PRAM; center problem; interval graph; circular-arc graph;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The center problem of a graph is motivated by a number of facility location problems. In this paper, we propose parallel algorithms for finding the center of interval graphs and circular-arc graphs. Our algorithms run in O(log n) time algorithm using O(n/ log n) processors while the intervals and arcs are given in sorted order. Our algorithms are on the EREW PRAM model.

引用

页码：2704 / 2709

页数：6

共 12 条

[1]

Akl S.G., 1997, Parallel Computation: Models and Methods

[2] FINDING LEVEL-ANCESTORS IN TREES [J].

BERKMAN, O ;

VISHKIN, U .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (02) :214-230

[3] Efficient algorithms for centers and medians in interval and circular-arc graphs [J].

Bespamyatnikh, S ;

Bhattacharya, B ;

Keil, M ;

Kirkpatrick, D ;

Segal, M .

NETWORKS, 2002, 39 (03) :144-152

[4]

CHAO HS, 2001, P JOINT M 5 WORLD MU, V7, P331

[5]

Chen DZ, 1998, NETWORKS, V31, P249, DOI 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO

[6]

2-D

[7] PARALLEL MERGE SORT [J].

COLE, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785

[8] TRAPEZOID GRAPHS AND THEIR COLORING [J].

DAGAN, I ;

GOLUMBIC, MC ;

PINTER, RY .

DISCRETE APPLIED MATHEMATICS, 1988, 21 (01) :35-46

[9]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[10] OPTIMAL PARALLEL ALGORITHMS FOR PROBLEMS MODELED BY A FAMILY OF INTERVALS [J].

OLARIU, S ;

SCHWING, JL ;

ZHANG, JY .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (03) :364-374

← 1 2 →