×

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Aleksandrov, L., Djidjev, H.: Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. Discrete Math. 9, 129–150 (1996) · Zbl 0847.05046
[3] 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)
[4] 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
[5] Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996) · Zbl 0864.68074
[6] Borie, R., Johnson, J.L., Raghavan, V., Spinrad, J.P.: Robust polynomial time algorithms on clique-width k graphs. Manuscript (2002)
[7] Brandstädt, A., Dragan, F.F., Nicolai, F.: LexBFS-orderings and powers of chordal graphs. Discrete Math. 171, 27–42 (1997) · Zbl 0880.05074
[8] Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8, 359–387 (1995) · Zbl 0832.05037
[9] 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
[10] 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
[11] Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discrete Appl. Math. 101, 77–114 (2000) · Zbl 0958.05105
[12] Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM J. Algebr. Discrete Methods 3, 229–240 (1982) · Zbl 0503.05057
[13] Djidjev, H.N.: A separator theorem for graphs of fixed genus. Serdica 11, 319–329 (1985) · Zbl 0602.05025
[14] 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
[15] 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
[16] Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discrete Math. 20, 241–260 (2006) · Zbl 1112.05025
[17] Elkin, M., Peleg, D.: Approximating k-spanner problems for k>2. Theor. Comput. Sci. 337, 249–277 (2005) · Zbl 1075.05082
[18] Elkin, M., Peleg, D.: (1+{\(\epsilon\)},{\(\beta\)})-Spanner constructions for general graphs. SIAM J. Comput. 33, 608–631 (2004) · Zbl 1056.05134
[19] 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
[20] 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)
[21] 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
[22] 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
[23] 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
[24] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054
[25] 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
[26] 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
[27] 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
[28] Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994) · Zbl 0825.68144
[29] Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 346–358 (1979) · Zbl 0432.05022
[30] Liestman, A.L., Shermer, T.: Additive graph spanners. Networks 23, 343–364 (1993) · Zbl 0783.68094
[31] Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13, 99–116 (1989) · Zbl 0673.05059
[32] 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
[33] 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
[34] Robertson, N., Seymour, P.D.: Graph minors II: Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986) · Zbl 0611.05017
[35] 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.