@inproceedings{9fcd18457c51435f8f7ee39f71cb1a5a,
title = "Efficient domination on permutation graphs and trapezoid graphs",
abstract = "The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m¯denotes the number of edges in the complement of G.",
author = "{Daniel Liang}, Y. and Lu, {Chin Lung} and Tang, {Chuan Yi}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd Annual International Computing and Combinatorics Conference, COCOON 1997 ; Conference date: 20-08-1997 Through 22-08-1997",
year = "1997",
language = "English",
isbn = "354063357X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "232--241",
editor = "Tao Jiang and D.T. Lee",
booktitle = "Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings",
address = "Germany",
}