An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

0.00 Avg rating0 Votes
Article ID: iaor2002362
Country: Netherlands
Volume: 102
Issue: 3
Start Page Number: 159
End Page Number: 173
Publication Date: Jun 2000
Journal: Discrete Applied Mathematics
Authors: , ,
Abstract:

Given a permutation graph G with its corresponding permutation π, 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(nloglogn) algorithm.

Reviews

Required fields are marked *. Your email address will not be published.