Abstract
This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most δ, i.e., the tree-length δ graphs. For such graphs we construct additive 2δ-spanners with O(δnlog n) edges, and additive 4δ-spanners with O(δn) edges. This provides new upper bounds for chordal graphs for which δ=1. We also show a lower bound, and prove that there are graphs of tree-length δ for which every multiplicative δ-spanner (and thus every additive (δ–1)-spanner) requires Ω(n 1 + 1/Θ(δ)) edges.
Supported by the European Research Training Network COMBSTRU-HPRN-CT-2002-00278.
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
Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graph and Combinatorics 18(1), 53–57 (2002)
Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9(1), 81–100 (1993)
Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k − 1)-spanner of O(n1 + 1/k) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 384–396. Springer, Heidelberg (2003)
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, 1305–1317 (1996)
Brandes, U., Handke, D.: NP-completeness results for minimum planar spanners. Discrete Mathematics & Theoretical Computer Science 3(1), 1–10 (1998)
Brandstädt, A., Dragan, F.F., Le, H.-O., Van Bang, L.: Tree spanners on chordal graphs: Complexity and algorithms. Theoretical Computer Science 310, 329–354 (2004)
Cai, L., Corneil, D.G.: Tree spanners. SIAM Journal on Discrete Mathematics 8(3), 359–387 (1995)
Chepoi, V.D., Dragan, F.F.: Distance approximating trees in graphs. In: Elsevier (ed.) 6th International Conference on Graph Theory (ICGT), August 2000. Electronical Notes in Discrete Mathematics (2000)
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. 96–107. Springer, Heidelberg (2003)
Diestel, R.: Graph Theory of Graduate Texts in Mathematics, 2nd edn., vol. 173. Springer, Heidelberg (February 2000)
Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 750–759 (1999)
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM Journal on Computing 29, 1740–1759 (2000)
Dourisboure, Y.: Routage compact et longueur arborescente. PhD thesis, Université Bordeaux 1, Talence, France (December 2003)
Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Improved spanners for bounded tree-length graphs (2004) (in preparation)
Dourisboure, Y., Gavoille, C.: Tree-decomposition of graphs with small diameter bags. In: 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), September 2003, pp. 100–104 (2003)
Elkin, M., Peleg, D. (1+,ε β)-spanner constructions for general graphs. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 173–182 (2001)
Erdös, P.: Extremal problems in graph theory. Publ. House Cszechoslovak Acad. Sci., Prague, 29–36 (1964)
Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Applied Mathematics 108, 85–103 (2001)
Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 476–488. Springer, Heidelberg (2001)
Madanlal, M.S., Venkatesan, G., Pandu Rangan, C.: Tree 3-spanners on interval, permutation and regular bipartite graphs. Information Processing Letters 59(2), 97–102 (1996)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)
Peleg, D., Schäffer, A.A.: Graph spanners. Journal of Graph Theory 13(1), 99–116 (1989)
Peleg, D., Ullman, J.D.: An optimal synchornizer for the hypercube. SIAM Journal on Computing 18, 740–747 (1989)
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM 36(3), 510–530 (1989)
Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 7, 309–322 (1986)
Soares, J.: Graphs spanners: A survey. Congressus Numerantium 89, 225–238 (1992)
Thorup, M., Zwick, U.: Approximate distance oracles. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 183–192 (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
Dourisboure, Y., Gavoille, C. (2004). Sparse Additive Spanners for Bounded Tree-Length Graphs. In: Královic̆, R., Sýkora, O. (eds) Structural Information and Communication Complexity. SIROCCO 2004. Lecture Notes in Computer Science, vol 3104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27796-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-27796-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22230-9
Online ISBN: 978-3-540-27796-5
eBook Packages: Springer Book Archive