Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars

References

• Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5):753–782.Crossref, Google Scholar
• Assmann SF, Peck GW, Sysło MM, Zak J (1981) The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Algebraic Discrete Methods 2(4):387–393.Crossref, Google Scholar
• Avram F, Bertsimas D (1992) The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach. Ann. Appl. Probab. 2(1):113–130.Crossref, Google Scholar
• Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Proc. Cambridge Philos. Soc. 55:299–327.Crossref, Google Scholar
• Boucheron S, Lugosi G, Bousquet O (2004) Concentration inequalities. Bousquet O, von Luxburg U, Rätsch G, eds. Advanced Lectures on Machine Learning, Vol. 3176, Lecture Notes in Comput. Sci. (Springer, Berlin), 208–240.Crossref, Google Scholar
• Cortina-Borja M, Robinson T (2000) Estimating the asymptotic constants of the total length of Euclidean minimal spanning trees with power-weighted edges. Statist. Probab. Lett. 47(2):125–128.Crossref, Google Scholar
• El-Basil S (1987) Applications of caterpillar trees in chemistry and physics. J. Math. Chemistry 1:153–174.Crossref, Google Scholar
• El-Basil S (1990) Caterpillar (Gutman) trees in chemical graph theory. Gutman I, Cyvin S, eds. Advances in the Theory of Benzenoid Hydrocarbons, Vol. 153, Topics in Current Chemistry (Springer, Berlin), 273–289.Crossref, Google Scholar
• El-Basil S (2008) Combinatorial properties of graphs and groups of physico-chemical interest. Combinatorial Chemistry and High Throughput Screening 11(9):707–722.Crossref, Google Scholar
• Feige U, Talwar K (2005) Approximating the bandwidth of caterpillars. Approximation, Randomization and Combinatorial Optimization, Vol. 3624, Lecture Notes in Comput. Sci. (Springer, Berlin), 62–73.Crossref, Google Scholar
• Few L (1955) The shortest path and the shortest road through n points in a region. Mathematika 2:141–144.Crossref, Google Scholar
• Finch SR (2003) Mathematical Constants. Encyclopedia of Mathematics and Its Applications, Vol. 94 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Gutman I (1977) Topological properties of benzenoid systems. Theoret Chemistry Accounts: Theory, Comput., Modeling (Theoretica Chimica Acta) 45:309–315.Google Scholar
• Haralambides J, Makedon F, Monien B (1991) Bandwidth minimization: An approximation algorithm for caterpillars. Math. Systems Theory 24(3):169–177.Crossref, Google Scholar
• Harary F, Schwenk A (1971) Trees with Hamiltonian square. Mathematika 18:138–140.Crossref, Google Scholar
• Harary F, Schwenk A (1972) A new crossing number for bipartite graphs. Utilitas Math. 1:203–209.Google Scholar
• Harary F, Schwenk AJ (1973) The number of caterpillars. Discrete Math. 6:359–365.Crossref, Google Scholar
• Johnson DS, McGeoch LA, Rothberg EE (1996) Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Tardos E, ed. Proc. Seventh Annual ACM-SIAM Sympos. Discrete Algorithms, Atlanta, GA (ACM, New York), 341–350.Google Scholar
• Kesten H, Lee S (1996) The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Probab. 6(2):495–527.Crossref, Google Scholar
• Korevaar J (2004) Tauberian theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Vol. 329 (Springer, Berlin).Crossref, Google Scholar
• Lin M, Lin Z, Xu J (2006) Graph bandwidth of weighted caterpillars. Theoret. Comput. Sci. 363(3):266–277.Crossref, Google Scholar
• Lindvall T (1992) Lectures on the Coupling Method (Dover Publications, Mineola, NY).Google Scholar
• Miller Z (1981) The bandwidth of caterpillar graphs. Hoffman F, Reid KB, Mullin RC, Stanton RG, eds., Proc. Twelfth Southeastern Conf. Combinatorics, Graph Theory Comput., Vol. 2, Baton Rouge, LA, Vol. 33 (Utilitas Mathematica Publications, Winnipeg, Canada), 235–252.Google Scholar
• Monien B (1986) The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods 7(4):505–512.Crossref, Google Scholar
• Moscato P, Norman MG (1998) On the performance of heuristics on finite and infinite fractal instances of the Euclidean traveling salesman problem. INFORMS J. Comput. 10(2):121–132.Link, Google Scholar
• Ortiz C, Villanueva M (2012) Maximal independent sets in caterpillar graphs. Discrete Appl. Math. 160(3):259–266.Crossref, Google Scholar
• Rhee WT (1993) A matching problem and subadditive Euclidean functionals. Ann. Appl. Probab. 3(3):794–801.Crossref, Google Scholar
• Steele JM (1981) Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab. 9(3):365–376.Crossref, Google Scholar
• Steele JM (1986) An Efron-Stein inequality for nonsymmetric statistics. Ann. Statist. 14(2):753–758.Crossref, Google Scholar
• Steele JM (1988) Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab. 16(4):1767–1787.Crossref, Google Scholar
• Steele JM (1997) Probability Theory and Combinatorial Optimization, Vol. 69, CBMS-NSF Regional Conference Series in Applied Mathematics (Society for Industrial and Applied Mathematics (SIAM), Philadelphia).Crossref, Google Scholar
• Tao T (2008) Structure and Randomness (American Mathematical Society, Providence, RI).Google Scholar
• Yukich JE (1998) Probability Theory of Classical Euclidean Optimization Problems, Vol. 1675, Lecture Notes in Mathematics (Springer, Berlin).Google Scholar