IMI/Publicaţii/CSJM/Ediţii/CSJM v.1, n.2 (2), 1993/

HT-graphs: centers, connected r-domination and Steiner trees

Authors: F. Dragan
Keywords: HT-graph, vertex elimination ordering, center, connected domination, Steiner tree, linear-time algorithm.


HT-graphs have been introduced in [11] and investigated with respect to location problems on graphs. In this paper two new characterizations of these graphs are given and then it is shown that the central vertex, connected r-domination and Steiner trees problems are linear or almost linear time solvable in HT-graphs.

Feodor Dragan,
Moldavian University,
A.Mateevici str. 60,
Department of Mathematics and Cybernetics,
Chisinau, 277009, Moldova


Adobe PDF document0.19 Mb