A linear-time algorithm for paired-domination problem in strongly chordal graphs

Lei Chen; Changhong Lu; Zhenbing Zeng

doi:10.1016/j.ipl.2009.09.014

A linear-time algorithm for paired-domination problem in strongly chordal graphs

Lei Chen, Changhong Lu, Zhenbing Zeng

School of Mathematical Sciences

East China Normal University

Research output: Contribution to journal › Article › peer-review

27 Scopus citations

Abstract

Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired-dominating set if every vertex in V - S has at least one neighbor in S and the induced subgraph G [S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.

Original language	English
Pages (from-to)	20-23
Number of pages	4
Journal	Information Processing Letters
Volume	110
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2009.09.014
State	Published - 1 Dec 2009

Keywords

Algorithms
Chordal graph
Combinatorial problems
Domination
Paired-domination
Strongly chordal graph

Access to Document

10.1016/j.ipl.2009.09.014

Cite this

@article{37ee67665d0e42a8800fb2e696b3767d,

title = "A linear-time algorithm for paired-domination problem in strongly chordal graphs",

abstract = "Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired-dominating set if every vertex in V - S has at least one neighbor in S and the induced subgraph G [S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.",

keywords = "Algorithms, Chordal graph, Combinatorial problems, Domination, Paired-domination, Strongly chordal graph",

author = "Lei Chen and Changhong Lu and Zhenbing Zeng",

year = "2009",

month = dec,

day = "1",

doi = "10.1016/j.ipl.2009.09.014",

language = "英语",

volume = "110",

pages = "20--23",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A linear-time algorithm for paired-domination problem in strongly chordal graphs

AU - Chen, Lei

AU - Lu, Changhong

AU - Zeng, Zhenbing

PY - 2009/12/1

Y1 - 2009/12/1

N2 - Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired-dominating set if every vertex in V - S has at least one neighbor in S and the induced subgraph G [S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.

AB - Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired-dominating set if every vertex in V - S has at least one neighbor in S and the induced subgraph G [S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.

KW - Algorithms

KW - Chordal graph

KW - Combinatorial problems

KW - Domination

KW - Paired-domination

KW - Strongly chordal graph

UR - https://www.scopus.com/pages/publications/70449530777

U2 - 10.1016/j.ipl.2009.09.014

DO - 10.1016/j.ipl.2009.09.014

M3 - 文章

AN - SCOPUS:70449530777

SN - 0020-0190

VL - 110

SP - 20

EP - 23

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

A linear-time algorithm for paired-domination problem in strongly chordal graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this