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.
|出版狀態||Published - 1 十二月 1998|
|事件||4th International Conference on Computer Science and Informatics, JCIS 1998 - Research Triangle Park, NC, United States|
持續時間: 23 十月 1998 → 28 十月 1998
|Conference||4th International Conference on Computer Science and Informatics, JCIS 1998|
|城市||Research Triangle Park, NC|
|期間||23/10/98 → 28/10/98|