A polynomial-time algorithm for the paired-domination problem on permutation graphs

Edwin Tai Chiu Cheng, Liying Kang, Erfang Shan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)


A set S of vertices in a graph H = (V, E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O (m n) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.
Original languageEnglish
Pages (from-to)262-271
Number of pages10
JournalDiscrete Applied Mathematics
Issue number2
Publication statusPublished - 28 Jan 2009


  • Algorithm
  • Paired-domination
  • Permutation graph

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Cite this