# zbMATH — the first resource for mathematics

Collective tree spanners in graphs with bounded parameters. (English) Zbl 1223.05247
Summary: In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph $$G=(V,E)$$ admits a system of $$\mu$$ collective additive tree $$r$$-spanners if there is a system $$\mathcal{T}(G)$$ of at most $$\mu$$ spanning trees of $$G$$ such that for any two vertices $$x,y$$ of $$G$$ a spanning tree $$T \in \mathcal{T}(G)$$ exists such that $$d_{T }(x,y) \leq d _{G}(x,y)+r$$.
We describe a general method for constructing a “small” system of collective additive tree $$r$$-spanners with small values of $$r$$ for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of $$O(\sqrt{n})$$ collective additive tree 0-spanners, any weighted graph with tree-width at most $$k-1$$ admits a system of $$k\log_{2}n$$ collective additive tree 0-spanners, any weighted graph with clique-width at most $$k$$ admits a system of $$k\log_{3/2}n$$ collective additive tree $$(2\mathsf{w})$$-spanners, and any weighted graph with size of largest induced cycle at most $$c$$ admits a system of $$\log_{2}n$$ collective additive tree $$(2\lfloor c/2\rfloor\mathsf{w})$$ -spanners and a system of $$4\log_{2}n$$ collective additive tree $$(2(\lfloor c/3\rfloor +1)\mathsf{w})$$-spanners (here, $$\mathsf{w}$$ is the maximum edge weight in $$G$$).
The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of $$4\log_{2}n$$ collective additive tree $$(2\mathsf{w})$$ -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.

##### MSC:
 05C75 Structural characterization of families of graphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C12 Distance in graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text:
##### References:
  Abraham, I., Gavoille, C., Malkhi, D.: Compact routing for graphs excluding a fixed minor. In: 19th International Symposium on Distributed Computing (DISC’05). Lecture Notes in Computer Science, vol. 3724, pp. 442–456. Springer, Berlin (2005) · Zbl 1171.68360  Aleksandrov, L., Djidjev, H.: Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. Discrete Math. 9, 129–150 (1996) · Zbl 0847.05046  Alon, N., Seymour, P., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 293–299. Assoc. Comput. Mach., New York (1990)  Bodlaender, H.L.: Discovering treewidth. In: SOFSEM 2005: Theory and Practice of Computer Science, 31st Conference on Current Trends in Theory and Practice of Computer Science, January 22–28, 2005. Lecture Notes in Computer Science, vol. 3381, pp. 1–16. Springer, Berlin (2005) · Zbl 1117.68451  Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996) · Zbl 0864.68074  Borie, R., Johnson, J.L., Raghavan, V., Spinrad, J.P.: Robust polynomial time algorithms on clique-width k graphs. Manuscript (2002)  Brandstädt, A., Dragan, F.F., Nicolai, F.: LexBFS-orderings and powers of chordal graphs. Discrete Math. 171, 27–42 (1997) · Zbl 0880.05074  Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8, 359–387 (1995) · Zbl 0832.05037  Chepoi, V.D., Dragan, F.F., Yan, C.: Additive spanners for k-chordal graphs. In: Proceedings of the 5th Conference on Algorithms and Complexity (CIAC 2003), May 28–30, 2003. Lecture Notes in Computer Science, vol. 2653, pp. 96–107. Springer, Berlin (2003) · Zbl 1032.68118  Corneil, D.G., Dragan, F.F., Köhler, E., Yan, C.: Collective tree 1-spanners for interval graphs. In: Proceedings of the 31st International Workshop Graph-Theoretic Concepts in Computer Science (WG’05), June 2005. Lecture Notes in Computer Science, vol. 3787, pp. 151–162. Springer, Berlin (2005) · Zbl 1171.05370  Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discrete Appl. Math. 101, 77–114 (2000) · Zbl 0958.05105  Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM J. Algebr. Discrete Methods 3, 229–240 (1982) · Zbl 0503.05057  Djidjev, H.N.: A separator theorem for graphs of fixed genus. Serdica 11, 319–329 (1985) · Zbl 0602.05025  Dragan, F.F., Yan, C.: Collective tree spanners in graphs with bounded genus, chordality, tree-width, or clique-width. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Hainan, China, December 19–21, 2005. Lecture Notes in Computer Science, vol. 3827, pp. 583–592. Springer, Berlin (2005) · Zbl 1175.68290  Dragan, F.F., Yan, C., Corneil, D.G.: Collective tree spanners and routing in AT-free related graphs. J. Graph Algorithms Appl. 10, 97–122 (2006) · Zbl 1161.68660  Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discrete Math. 20, 241–260 (2006) · Zbl 1112.05025  Elkin, M., Peleg, D.: Approximating k-spanner problems for k>2. Theor. Comput. Sci. 337, 249–277 (2005) · Zbl 1075.05082  Elkin, M., Peleg, D.: (1+{$$\epsilon$$},{$$\beta$$})-Spanner constructions for general graphs. SIAM J. Comput. 33, 608–631 (2004) · Zbl 1056.05134  Emek, Y., Peleg, D.: Approximating minimum max-stretch spanning trees on unweighted graphs. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, USA, January 11–14, 2004, pp. 261–270. SIAM, Philadelphia (2004) · Zbl 1317.68275  Engelfriet, J., Rozenberg, G.: Node replacement graph grammars. In: Handbook of Graph Grammars and Computing by Graph Transformation, Foundations, vol. I, pp. 1–94. World Scientific, Singapore (1997)  Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proceedings of the 28th Int. Colloquium on Automata, Languages and Programming (ICALP 2001). Lecture Notes in Computer Science, vol. 2076, pp. 757–772. Springer, Berlin (2001) · Zbl 0987.68001  Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms 5, 391–407 (1984) · Zbl 0556.05022  Gilbert, J.R., Rose, D.J., Edenbrandt, A.: A separator theorem for chordal graphs. SIAM J. Algebr. Discrete Methods 5, 306–313 (1984) · Zbl 0551.05049  Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054  Golumbic, M.C., Rotics, U.: On the clique-width of perfect graph classes. In: Proceedings of the 25th International Workshop Graph-Theoretic Concepts in Computer Science (WG ’99), Ascona, Switzerland, June 1999. Lecture Notes in Computer Science, vol. 1665, pp. 135–147. Springer, Berlin (1999) · Zbl 0941.05047  Gupta, A., Kumar, A., Rastogi, R.: Traveling with a pez dispenser (or, routing issues in MPLS). SIAM J. Comput. 34, 453–474 (2005). Appeared also in FOCS 2001 · Zbl 1087.68013  Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234, 59–84 (2000) · Zbl 0945.68189  Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994) · Zbl 0825.68144  Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 346–358 (1979) · Zbl 0432.05022  Liestman, A.L., Shermer, T.: Additive graph spanners. Networks 23, 343–364 (1993) · Zbl 0783.68094  Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13, 99–116 (1989) · Zbl 0673.05059  Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proceedings of the 6th ACM Symposium on Principles of Distributed Computing, Vancouver, pp. 77–85 (1987) · Zbl 0681.68091  Prisner, E., Kratsch, D., Le, H.-O., Müller, H., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math. 17, 332–340 (2003) · Zbl 1041.05024  Robertson, N., Seymour, P.D.: Graph minors II: Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986) · Zbl 0611.05017  Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th Ann. ACM Symp. on Par. Alg. and Arch. (SPAA 2001), pp. 1–10. Assoc. Comput. Mach., New York (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.