The on-line dominating set problem for permutation graphs was studied. The performance ratio of an on-line algorithm was also calculated. The performance ratio was found to be the minimum dominating set of the permutation graph. The on-line algorithm depended on the performance ratio. The algorithm was better when the performance ratio was small. Amortized analysis was used by assigning vertices of the permutation graph in a dominaing set to vertices in a minimum dominating set.
|Number of pages||4|
|State||Published - 1 Dec 1998|
|Event||4th International Conference on Computer Science and Informatics, JCIS 1998 - Research Triangle Park, NC, United States|
Duration: 23 Oct 1998 → 28 Oct 1998
|Conference||4th International Conference on Computer Science and Informatics, JCIS 1998|
|City||Research Triangle Park, NC|
|Period||23/10/98 → 28/10/98|