Computer Science Journal of Moldova (Jun 1993)

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

  • F. Dragan

Journal volume & issue
Vol. 1, no. 2(2)
pp. 64 – 83

Abstract

Read online

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.

Keywords