STEINER SET AND CONNECTED DOMINATION IN TRAPEZOID GRAPHS

Authors
LIANG YD
Citation
Yd. Liang, STEINER SET AND CONNECTED DOMINATION IN TRAPEZOID GRAPHS, Information processing letters, 56(2), 1995, pp. 101-108
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
2
Year of publication
1995
Pages
101 - 108
Database
ISI
SICI code
0020-0190(1995)56:2<101:SSACDI>2.0.ZU;2-T
Abstract
Trapezoid graphs are extensions of interval graphs and permutation gra phs. This paper presents an O(\V\) time algorithm for finding a minimu m cardinality Steiner set and an O(\E\ + \V\) time algorithm for findi ng a minimum cardinality connected dominating set in a trapezoid graph G = (V, E), given the trapezoid diagram.