Abstract
Farber and Keil presented an O( n 3 algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.
Original language | American English |
---|---|
Journal | Information Processing Letters |
Volume | 37 |
DOIs | |
State | Published - Feb 28 1991 |
Disciplines
- Computer Sciences
Keywords
- Algorithm analysis
- minimum weight dominating set
- permutation graph