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

Edwin Tai Chiu Cheng; Liying Kang; Erfang Shan

doi:10.1016/j.dam.2008.02.015

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

Edwin Tai Chiu Cheng, Liying Kang, Erfang Shan

Research output: Journal article publication › Journal article › Academic research › peer-review

24 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	262-271
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	157
Issue number	2
DOIs	https://doi.org/10.1016/j.dam.2008.02.015
Publication status	Published - 28 Jan 2009

Keywords

Algorithm
Paired-domination
Permutation graph

ASJC Scopus subject areas

Applied Mathematics
Discrete Mathematics and Combinatorics

More information

10.1016/j.dam.2008.02.015

http://hdl.handle.net/10397/479

Cite this

@article{bed4e00a9a5d48ffaa2f12cee32d7547,

title = "A polynomial-time algorithm for the paired-domination problem on permutation graphs",

abstract = "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.",

keywords = "Algorithm, Paired-domination, Permutation graph",

author = "Cheng, {Edwin Tai Chiu} and Liying Kang and Erfang Shan",

year = "2009",

month = jan,

day = "28",

doi = "10.1016/j.dam.2008.02.015",

language = "English",

volume = "157",

pages = "262--271",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

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

AU - Cheng, Edwin Tai Chiu

AU - Kang, Liying

AU - Shan, Erfang

PY - 2009/1/28

Y1 - 2009/1/28

N2 - 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.

AB - 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.

KW - Algorithm

KW - Paired-domination

KW - Permutation graph

UR - http://www.scopus.com/inward/record.url?scp=56349153226&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.02.015

DO - 10.1016/j.dam.2008.02.015

M3 - Journal article

SN - 0166-218X

VL - 157

SP - 262

EP - 271

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this