Paired domination on interval and circular-arc graphs

Edwin Tai Chiu Cheng; L. Y. Kang; Chi To Ng

doi:10.1016/j.dam.2007.05.011

Paired domination on interval and circular-arc graphs

Edwin Tai Chiu Cheng, L. Y. Kang, Chi To Ng

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

42 Citations (Scopus)

Abstract

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O (m + n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O (m (m + n)) time.

Original language	English
Pages (from-to)	2077-2086
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	155
Issue number	16
DOIs	https://doi.org/10.1016/j.dam.2007.05.011
Publication status	Published - 1 Oct 2007

Keywords

Circular-arc graph
Interval graph
Paired domination

ASJC Scopus subject areas

Computational Theory and Mathematics
Applied Mathematics
Discrete Mathematics and Combinatorics
Theoretical Computer Science

More information

10.1016/j.dam.2007.05.011

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

Cite this

@article{61fdae5f33684e33a1519230446b6eb0,

title = "Paired domination on interval and circular-arc graphs",

abstract = "We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O (m + n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O (m (m + n)) time.",

keywords = "Circular-arc graph, Interval graph, Paired domination",

author = "Cheng, {Edwin Tai Chiu} and Kang, {L. Y.} and Ng, {Chi To}",

year = "2007",

month = oct,

day = "1",

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

language = "English",

volume = "155",

pages = "2077--2086",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "16",

}

TY - JOUR

T1 - Paired domination on interval and circular-arc graphs

AU - Cheng, Edwin Tai Chiu

AU - Kang, L. Y.

AU - Ng, Chi To

PY - 2007/10/1

Y1 - 2007/10/1

N2 - We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O (m + n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O (m (m + n)) time.

AB - We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O (m + n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O (m (m + n)) time.

KW - Circular-arc graph

KW - Interval graph

KW - Paired domination

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

U2 - 10.1016/j.dam.2007.05.011

DO - 10.1016/j.dam.2007.05.011

M3 - Journal article

SN - 0166-218X

VL - 155

SP - 2077

EP - 2086

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 16

ER -

Paired domination on interval and circular-arc graphs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this