ISSN:
1432-0541
Keywords:
Dominating set
;
Permutation graphs
;
Dynamic programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract AnO(n log logn) (resp.O(n2 log2 n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n2 (resp.O(n3)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01190158
Permalink