Abstract
In this paper we introduce a new notion of collective tree spanners. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system \(\mathcal{T}(G)\) of at most μ 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)≤ d G (x,y)+r. Among other results, we show that any chordal graph, chordal bipartite graph or cocomparability graph admits a system of at most log2 n collective additive tree 2–spanners and any c-chordal graph admits a system of at most log2 n collective additive tree (2\(\lfloor c/2\rfloor\))–spanners. Towards establishing these results, we present a general property for graphs, called (α,r)–decomposition, and show that any (α,r)–decomposable graph G with n vertices admits a system of at most log1/α n collective additive tree 2r–spanners. We discuss also an application of the collective tree spanners to the problem of designing compact and efficient routing schemes in graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 161–168 (1998)
Berge, C.: Hypergraphs. North-Holland, Amsterdam (1989)
Brandstädt, F.F., Dragan, H.-O.: Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 163–174. Springer, Heidelberg (2002)
Brandstädt, F.F., Dragan, H.-O., Le, V.B.: Tree spanners for bipartite graphs and probe interval graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 106–118. Springer, Heidelberg (2003)
Brandstädt, V.B., Le, J.: Graph Classes: A Survey. SIAM, Philadelphia (1999)
Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Disc. Math., 8, 359–387 (1995)
Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a Finite Metric by a Small Number of Tree Metrics. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 379–388 (1998)
Chepoi, V.D., Dragan, F.F., Yan, C.: Additive Spanners for k-Chordal Graphs. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 201–212. Springer, Heidelberg (2003)
Dragan, F.F., Lomonosov, I.: Compact and efficient routing schemes for special graph classes (2004) (in preparation)
Dragan, F.F., Yan, C.: Collective tree spanners of homogeneously orderable graphs (2004) (in preparation)
Dragan, F.F., Yan, C., Corneil, D.G.: Collective tree spanners and routing in AT-free related graphs (2004) (in preparation)
Dourisboure, Y., Gavoille, C.: Improved Compact Routing Scheme for Chordal Graphs. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 252–264. Springer, Heidelberg (2002)
Dourisboure, Y., Gavoille, C.: Tree-length of graphs (2003)(manuscript)
Fraigniaud, P., Gavoille, C.: Routing in Trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 757–772. Springer, Heidelberg (2001)
Gavoille, C., Gengler, M.: Space-efficiency of routing schemes of stretch factor three. J. Parallel and Distr. Comput. 61, 679–687 (2001)
Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 516–528. Springer, Heidelberg (2000)
Liestman, A.L., Shermer, T.: Additive graph spanners. Networks 23, 343–364 (1993)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. In: SIAM Monographs on Discrete Math. Appl., SIAM, Philadelphia (2000)
Peleg, D., Schäffer, A.A.: Graph Spanners. J. Graph Theory 13, 99–116 (1989)
Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proc. 6th ACM Symposium on Principles of Distributed Computing, Vancouver, pp. 77–85 (1987)
Prisner, E., Kratsch, D., Le, H.-O., Müller, H., Wagner, D.: Additive tree spanners. SIAM Journal on Discrete Mathematics 17, 332–340 (2003)
Thorup, M., Zwick, U.: Compact routing schemes. In: Thorup, M., Zwick, U. (eds.) Proc. 13th Ann. ACM Symp. on Par. Alg. and Arch (SPAA 2001), pp. 1–10. ACM Press, New York (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dragan, F.F., Yan, C., Lomonosov, I. (2004). Collective Tree Spanners of Graphs. In: Hagerup, T., Katajainen, J. (eds) Algorithm Theory - SWAT 2004. SWAT 2004. Lecture Notes in Computer Science, vol 3111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27810-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-27810-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22339-9
Online ISBN: 978-3-540-27810-8
eBook Packages: Springer Book Archive