Tree spanners on chordal graphs: complexity and algorithms

B. Awerbuch, A. Baratz, D. Peleg, Efficient broadcast and light-weighted spanners, manuscript, 1992. Bandelt, 1986, Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math., 7, 309, 10.1016/0196-8858(86)90038-2 Brandstädt, 1999, Distance approximating trees for chordal and dually chordal graphs, J. Algorithms, 30, 166, 10.1006/jagm.1998.0962 A. Brandstädt, V.B. Le, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications SIAM, Philadelphia, 1999. Buneman, 1974, A characterization of rigid circuit graphs, Discrete Math., 9, 48, 10.1016/0012-365X(74)90002-8 L. Cai, Tree spanners: spanning trees that approximate the distances, Ph.D. Thesis, University of Toronto, 1992. Cai, 1992, Tree spanners, Congressus Numer., 88, 65 Cai, 1995, Tree spanners, SIAM J. Discrete. Math., 8, 359, 10.1137/S0895480192237403 Chang, 1984, The k-domination and k-stability problems on sun-free chordal graphs, SIAM. J. Alg. Disc. Meth., 5, 332, 10.1137/0605034 Chepoi, 1988, Centers of triangulated graphs, Math. Notes, 43, 82, 10.1007/BF01139575 V.D. Chepoi, F.F. Dragan, Linear-time algorithm for finding a center vertex of a chordal graph, Lecture Notes in Computer Science, Vol. 855, Springer, Berlin, 1994, pp. 159–170. E. Dahlhaus, Chordale Graphen in besonderem Hinblick auf parallele Algorithmen, Habilitation Thesis, Universität Bonn, 1991. F.F. Dragan, A. Brandstädt, r-Dominating cliques in Helly graphs and chordal graphs, Proc. of the 11th STACS, Caen, France, Springer, Lecture Notes in Computer Science, Vol. 775, Springer, Berlin, 1994, pp. 735-746 Discrete Math. 162 (1996) 93-108. Farber, 1983, Characterizations of strongly chordal graphs, Discrete Math., 43, 173, 10.1016/0012-365X(83)90154-1 Farber, 1986, Convexity in graphs and hypergraphs, SIAM J. Alg. Discr. Meth., 7, 433, 10.1137/0607049 Fekete, 2001, Tree spanners in planar graphs, Discrete Appl. Math., 108, 85, 10.1016/S0166-218X(00)00226-2 Gavril, 1974, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory (B), 16, 47, 10.1016/0095-8956(74)90094-X Golumbic, 1980 Hoàng-Oanh Le, Effiziente Algorithmen für Baumspanner in chordalen Graphen, Diploma Thesis, Department of Mathematics, Technical University of Berlin, 1994. Le, 1999, Optimal tree 3-spanners in directed path graphs, Networks, 34, 81, 10.1002/(SICI)1097-0037(199909)34:2<81::AID-NET1>3.0.CO;2-P Howorka, 1981, A characterization of ptolemaic graphs, J. Graph Theory, 5, 323, 10.1002/jgt.3190050314 Madanlal, 1996, Tree 3-spanners on interval, permutation and regular bipartite graphs, Inform. Process. Lett., 59, 97, 10.1016/0020-0190(96)00078-6 I.E. Papoutsakis, Two structure theorems on tree spanners, M.Sc. Thesis, Department of Computer Science, University of Toronto, 1999. I.E. Papoutsakis, On the union of two tree spanners of a graph, Sixth Internat. Conf. on Graphs Theory Marseilles, France, August 28–September 1, 2000. D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Application, SIAM, Philadelphia, 2000. Peleg, 1989, Graph spanners, J. Graph Theory, 13, 99, 10.1002/jgt.3190130114 E. Prisner, Distance approximating spanning trees, in: Proc. STACS’97, Lecture Notes in Computer Science, Vol. 1200, Springer, Berlin, 1997, pp. 99–510. Soares, 1992, Graph spanners, Congressus Numer., 89, 225 Venkatesan, 1997, Restrictions of minimum spanner problems, Inform. Comput., 136, 143, 10.1006/inco.1997.2641 V.I. Voloshin, On properties of triangulated graphs, Oper. Res. Prog. (Kishinev), (1982) 24–32, (in Russian). J.R. Walter, Representations of rigid cycle graphs, Ph.D. Thesis, Wayne State University, Detroit, 1972.