Premium
A linear‐time algorithm for connected r ‐domination and Steiner tree on distance‐hereditary graphs
Author(s) -
Brandstädt Andreas,
Dragan Feodor F.
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199805)31:3<177::aid-net4>3.0.co;2-c
Subject(s) - combinatorics , mathematics , steiner tree problem , dominating set , cardinality (data modeling) , connectivity , graph , path (computing) , distance , discrete mathematics , computer science , shortest path problem , vertex (graph theory) , data mining , programming language
A distance‐hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r ‐dominating set and Steiner tree problems on distance‐hereditary graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 177–182, 1998