Parallel algorithms for the domination problems in trapezoid graphs

Y. Daniel Liang

doi:10.1016/S0166-218X(96)00052-2

Parallel algorithms for the domination problems in trapezoid graphs

Y. Daniel Liang

Computer Science

Indiana Purdue Univ at Fort Wayne

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

2 Scopus citations

Abstract

Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O(log² n) time on a EREW PRAM. The number of processors required is O(max{n³ log² n.n^2.376}) for the independent domination problem, and O(max {nm²/ log² n.m^2.376 }) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.

Original language	English
Pages (from-to)	241-249
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	74
Issue number	3
DOIs	https://doi.org/10.1016/S0166-218X(96)00052-2
State	Published - May 2 1997

Keywords

Connected domination
Domination
Independent domination
Parallel algorithm
Total domination
Trapezoid graph

Access to Document

10.1016/S0166-218X(96)00052-2

Cite this

@article{a066d48e04334d39b08163b0f2381441,

title = "Parallel algorithms for the domination problems in trapezoid graphs",

abstract = "Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O(log2 n) time on a EREW PRAM. The number of processors required is O(max{n3 log2 n.n2.376}) for the independent domination problem, and O(max {nm2/ log2 n.m2.376 }) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.",

keywords = "Connected domination, Domination, Independent domination, Parallel algorithm, Total domination, Trapezoid graph",

author = "Liang, {Y. Daniel}",

note = "Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O( log 2 n) time on a EREW PRAM.",

year = "1997",

month = may,

day = "2",

doi = "10.1016/S0166-218X(96)00052-2",

language = "English",

volume = "74",

pages = "241--249",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Parallel algorithms for the domination problems in trapezoid graphs

AU - Liang, Y. Daniel

N1 - Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O( log 2 n) time on a EREW PRAM.

PY - 1997/5/2

Y1 - 1997/5/2

N2 - Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O(log2 n) time on a EREW PRAM. The number of processors required is O(max{n3 log2 n.n2.376}) for the independent domination problem, and O(max {nm2/ log2 n.m2.376 }) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.

AB - Trapezoid graphs are a superclass of permutation graphs and interval graphs. This paper presents first parallel algorithms for the independent domination, total domination, connected domination and domination problems in weighted trapezoid graphs. All these algorithms take O(log2 n) time on a EREW PRAM. The number of processors required is O(max{n3 log2 n.n2.376}) for the independent domination problem, and O(max {nm2/ log2 n.m2.376 }) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.

KW - Connected domination

KW - Domination

KW - Independent domination

KW - Parallel algorithm

KW - Total domination

KW - Trapezoid graph

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

U2 - 10.1016/S0166-218X(96)00052-2

DO - 10.1016/S0166-218X(96)00052-2

M3 - Article

SN - 0166-218X

VL - 74

SP - 241

EP - 249

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -

Parallel algorithms for the domination problems in trapezoid graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this