Steiner Set and Connected Domination in Trapezoid Graphs

Y. Daniel Liang

doi:10.1016/0020-0190(95)00118-V

Steiner Set and Connected Domination in Trapezoid Graphs

Y. Daniel Liang

Computer Science

Indiana Purdue Univ at Fort Wayne

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

15 Scopus citations

Abstract

Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an ¦¦O(¦V¦) time algorithm for finding a minimum cardinality Steiner set and an ¦¦¦¦O(¦E¦ + ¦V¦) time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V , E ), given the trapezoid diagram.

Original language	American English
Journal	Information Processing Letters
Volume	56
DOIs	https://doi.org/10.1016/0020-0190(95)00118-V
State	Published - Oct 27 1995

Disciplines

Computer Sciences

Keywords

Algorithms
Breadth-first search
Combinatorial problems
Connected domination
Steiner set
Trapezoid graph

Access to Document

10.1016/0020-0190(95)00118-VLicense: Unspecified

Cite this

@article{44fc69831cbd4653ba3c006beb91d895,

title = "Steiner Set and Connected Domination in Trapezoid Graphs",

abstract = " Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an ¦¦O(¦V¦) time algorithm for finding a minimum cardinality Steiner set and an ¦¦¦¦O(¦E¦ + ¦V¦) time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V , E ), given the trapezoid diagram. ",

keywords = "Algorithms, Breadth-first search, Combinatorial problems, Connected domination, Steiner set, Trapezoid graph",

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

note = "Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an time algorithm for finding a minimum cardinality Steiner set and an time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V, E), given the trapezoid diagram.",

year = "1995",

month = oct,

day = "27",

doi = "10.1016/0020-0190(95)00118-V",

language = "American English",

volume = "56",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Steiner Set and Connected Domination in Trapezoid Graphs

AU - Liang, Y. Daniel

N1 - Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an time algorithm for finding a minimum cardinality Steiner set and an time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V, E), given the trapezoid diagram.

PY - 1995/10/27

Y1 - 1995/10/27

N2 - Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an ¦¦O(¦V¦) time algorithm for finding a minimum cardinality Steiner set and an ¦¦¦¦O(¦E¦ + ¦V¦) time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V , E ), given the trapezoid diagram.

AB - Trapezoid graphs are extensions of interval graphs and permutation graphs. This paper presents an ¦¦O(¦V¦) time algorithm for finding a minimum cardinality Steiner set and an ¦¦¦¦O(¦E¦ + ¦V¦) time algorithm for finding a minimum cardinality connected dominating set in a trapezoid graph G = ( V , E ), given the trapezoid diagram.

KW - Algorithms

KW - Breadth-first search

KW - Combinatorial problems

KW - Connected domination

KW - Steiner set

KW - Trapezoid graph

UR - https://www.sciencedirect.com/science/article/abs/pii/002001909500118V

U2 - 10.1016/0020-0190(95)00118-V

DO - 10.1016/0020-0190(95)00118-V

M3 - Article

SN - 0020-0190

VL - 56

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Steiner Set and Connected Domination in Trapezoid Graphs

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this