Linear algorithms for two independent set problems in permutation graphs

Y. Daniel Liang, Chongkye Rhee

Research output: Contribution to book or proceedingConference articlepeer-review

4 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - ACM Computer Science Conference
PublisherPubl by ACM
Pages90-93
Number of pages4
ISBN (Print)0897916344, 9780897916349
DOIs
StatePublished - 1994
EventProceedings of the 22nd Annual ACM Computer Science Conference - Phoenix, AZ, USA
Duration: Mar 8 1994Mar 10 1994

Publication series

NameProceedings - ACM Computer Science Conference

Conference

ConferenceProceedings of the 22nd Annual ACM Computer Science Conference
CityPhoenix, AZ, USA
Period03/8/9403/10/94

Scopus Subject Areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Linear algorithms for two independent set problems in permutation graphs'. Together they form a unique fingerprint.

Cite this