A LINEAR-TIME ALGORITHM FOR CONNECTED R-DOMINATION AND STEINER TREE ON DISTANCE-HEREDITARY GRAPHS

Authors
BRANDSTADT A DRAGAN FF
Citation
A. Brandstadt et Ff. Dragan, A LINEAR-TIME ALGORITHM FOR CONNECTED R-DOMINATION AND STEINER TREE ON DISTANCE-HEREDITARY GRAPHS, Networks, 31(3), 1998, pp. 177-182
Citations number
14
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
31
Issue
3
Year of publication
1998
Pages
177 - 182
Database
ISI
SICI code
0028-3045(1998)31:3<177:ALAFCR>2.0.ZU;2-M
Abstract
A distance-hereditary graph is a connected graph in which every induce d path is isometric, i.e., the distance of any two vertices in an indu ced 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. (C) 1998 John Wiley & Sons, Inc.