@inproceedings{fc58e61b1d474bb69f8fe17e2d31904c,
title = "Linear algorithms for two independent set problems in permutation graphs",
abstract = "We present O (|V| + |E|) time algorithms for the maximum weight independent set and minimum weight independent dominating set problems in permutation graphs G = (V, E), where an arbitrary weight is assigned to each vertex in V. It is known that the former problem can be solved in O(|V| loglog |V|) time and the latter in O (|V| log |V|) time. Our algorithms are linear to the number of vertices and edges, and are particularly good for sparse permutation graphs.",
author = "Liang, {Y. Daniel} and Chongkye Rhee",
year = "1994",
doi = "10.1145/197530.197561",
language = "English",
isbn = "0897916344",
series = "Proceedings - ACM Computer Science Conference",
publisher = "Publ by ACM",
pages = "90--93",
booktitle = "Proceedings - ACM Computer Science Conference",
note = "Proceedings of the 22nd Annual ACM Computer Science Conference ; Conference date: 08-03-1994 Through 10-03-1994",
}