A New Approach for the Domination Problem on Permutation Graphs

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

Farber and Keil presented an O( n 3  algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where  m  is the number of edges in a permutation graph  G  of  n  nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.
Original languageAmerican English
JournalInformation Processing Letters
Volume37
DOIs
StatePublished - Feb 28 1991

Disciplines

  • Computer Sciences

Keywords

  • Algorithm analysis
  • minimum weight dominating set
  • permutation graph

Fingerprint

Dive into the research topics of 'A New Approach for the Domination Problem on Permutation Graphs'. Together they form a unique fingerprint.

Cite this