Given a permutation graph G with its corresponding permutation pi, we present an algorithm for finding a minimum cardinality dominating set for G. Our algorithm runs in O(n) time in amortized sense where n is the number of vertices in G. Hence, it is optimal. The best previous result is an O(n log log n) algorithm. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 14]
展开▼
