Tight Bound for the On-line Dominating Set Problem of Permutation Graphs (extended abstract)

Wen-Guey Tzeng*

*此作品的通信作者

研究成果: Paper同行評審

摘要

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.

原文English
頁面130-133
頁數4
出版狀態Published - 1 十二月 1998
事件4th International Conference on Computer Science and Informatics, JCIS 1998 - Research Triangle Park, NC, United States
持續時間: 23 十月 199828 十月 1998

Conference

Conference4th International Conference on Computer Science and Informatics, JCIS 1998
國家/地區United States
城市Research Triangle Park, NC
期間23/10/9828/10/98

引用此