NC algorithms for dominations in permutation graphs

Y. D. Liang, C. Rhee, S. K. Dhall, S. Lakshmivarahan

Research output: Contribution to book or proceedingConference articlepeer-review

Abstract

In this paper, we present NC algorithms for finding minimum weight independent dominating set (MWIDS), minimum weight total dominating set (MWTDS), and minimum weight connected dominating set (MWCDS) for permutation graphs. All these algorithms take O(log 2n) time on CREW PRAM. The number of processor required is n3/logn for finding MWIDS, and m3/logm for finding MWTDS and MWCDS, where m is the number of edges in a permutation graph of n nodes.

Original languageEnglish
Title of host publicationApplied Computing
Subtitle of host publicationTechnological Challenges of the 1990's
PublisherPubl by ACM
Pages734-739
Number of pages6
ISBN (Print)089791502X, 9780897915021
DOIs
StatePublished - 1992
EventProceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing - SAC '92 - Kansas City, KS, USA
Duration: Mar 1 1992Mar 3 1992

Publication series

NameApplied Computing: Technological Challenges of the 1990's

Conference

ConferenceProceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing - SAC '92
CityKansas City, KS, USA
Period03/1/9203/3/92

Scopus Subject Areas

  • General Engineering

Fingerprint

Dive into the research topics of 'NC algorithms for dominations in permutation graphs'. Together they form a unique fingerprint.

Cite this