THE MINIMUM WEIGHT DOMINATING SET PROBLEM FOR PERMUTATION GRAPHS IS IN NC

Authors
RHEE C DHALL SK LAKSHMIVARAHAN S
Citation
C. Rhee et al., THE MINIMUM WEIGHT DOMINATING SET PROBLEM FOR PERMUTATION GRAPHS IS IN NC, Journal of parallel and distributed computing, 28(2), 1995, pp. 109-112
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
28
Issue
2
Year of publication
1995
Pages
109 - 112
Database
ISI
SICI code
0743-7315(1995)28:2<109:TMWDSP>2.0.ZU;2-M
Abstract
In this paper, we show that the problem of finding a minimum weight do minating set in a permutation graph, where a positive weight is assign ed to each vertex, is in NC by presenting an O(log n) parallel algorit hm with polynomially many processors on the CRCW model. (C) 1995 Acade mic Press, Inc.