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

Wen-Guey Tzeng*

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

Abstract

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.

Original languageEnglish
Pages130-133
Number of pages4
StatePublished - 1 Dec 1998
Event4th International Conference on Computer Science and Informatics, JCIS 1998 - Research Triangle Park, NC, United States
Duration: 23 Oct 199828 Oct 1998

Conference

Conference4th International Conference on Computer Science and Informatics, JCIS 1998
CountryUnited States
CityResearch Triangle Park, NC
Period23/10/9828/10/98

Cite this