AN O(N-TIME ALGORITHM FOR FINDING A MINIMUM-WEIGHT DOMINATING SET IN A PERMUTATION GRAPH(M))

Authors
RHEE C LIANG YD DHALL SK LAKSHMIVARAHAN S
Citation
C. Rhee et al., AN O(N-TIME ALGORITHM FOR FINDING A MINIMUM-WEIGHT DOMINATING SET IN A PERMUTATION GRAPH(M)), SIAM journal on computing, 25(2), 1996, pp. 404-419
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
25
Issue
2
Year of publication
1996
Pages
404 - 419
Database
ISI
SICI code
0097-5397(1996)25:2<404:AOAFFA>2.0.ZU;2-L
Abstract
Farber and Keil [Algorithmica, 4 (1989), pp. 221-236] presented an O(n (3))-time algorithm for finding a minimum-weight dominating set in per mutation graphs. This result was improved to O(n(2) log(2) n) by Tsai and Hsu [SIGAL '90 Algorithms, Lecture Notes in Computer Science, Spri nger-Verlag, New York, 1990, pp. 109-117] and to O(n(n + m)) by the au thors of this paper [Inform. Process. Lett., 37 (1991), pp. 219-224], respectively. In this paper, we introduce a new faster algorithm that takes only O(n + rn) time to solve the same problem, where m is the nu mber of edges in a graph of n vertices.