Name
Title | ||
|---|---|---|
An O(N+M)-Time Algorithm For Finding A Minimum-Weight Dominating Set In A Permutation Graph |
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 permutation graphs. This result was improved to O(n(2) log(2) n) by Tsai and Hsu [SIGAL '90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109-117] and to O(n(n + m)) by the authors 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 number of edges in a graph of n vertices. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1137/S0097539794200383 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
algorithm, dominating set, permutation graph | Journal | 25 |
Issue | ISSN | Citations |
2 | 0097-5397 | 3 |
PageRank | References | Authors |
0.51 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chong Jye Rhee | 1 | 31 | 11.62 |
| Y. Daniel Liang | 2 | 153 | 14.93 |
| Sudarshan K. Dhall | 3 | 522 | 60.65 |
| S. Lakshmivarahan | 4 | 412 | 66.03 |