×

Shape measures of random increasing \(k\)-trees. (English) Zbl 1372.60009

Summary: Random increasing \(k\)-trees represent an interesting and useful class of strongly dependent graphs that have been studied widely, including being used recently as models for complex networks. In this paper we study an informative notion called BFS-profile and derive, by several analytic means, asymptotic estimates for its expected value, together with the limiting distribution in certain cases; some interesting consequences predicting more precisely the shapes of random \(k\)-trees are also given. Our methods of proof rely essentially on a bijection between \(k\)-trees and ordinary trees, the resolution of linear systems, and a specially framed notion called Flajolet-Odlyzko admissibility.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrade, J. S. Jr; Herrmann, H. J.; Andrade, R. F. S.; da Silva, L. R., Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs, Phys. Rev. Lett., 94, pp., (2005)
[2] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284, (1987) · Zbl 0611.05022
[3] Arya, S.; Golin, M. J.; Mehlhorn, K., On the expected depth of random circuits, Combin. Probab. Comput., 8, 209-228, (1999) · Zbl 0941.68001
[4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[5] Beineke, L. W.; Pippert, R. E., The number of labeled k-dimensional trees, J. Combin. Theory, 6, 200-205, (1969) · Zbl 0175.20904
[6] Bergeron, F.; Flajolet, P.; Salvy, B., CAAP ’92, Varieties of increasing trees, 24-48, (1992), Springer
[7] Berztiss, A. T., Depth-first k-trees and critical path analysis, Acta Inform., 13, 325-346, (1980) · Zbl 0431.68064
[8] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Phys. Rep., 424, 175-308, (2006) · Zbl 1371.82002
[9] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G., The degree sequence of a scale-free random graph process, Random Struct. Alg., 18, 279-290, (2001) · Zbl 0985.05047
[10] Chauvin, B.; Klein, T.; Marckert, J.-F.; Rouault, A., Martingales and profile of binary search trees, Electron. J. Probab., 10, 420-435, (2005) · Zbl 1109.60059
[11] Chern, H.-H.; Hwang, H.-K., Phase changes in random m-ary search trees and generalized quicksort, Random Struct. Alg., 19, 316-358, (2001) · Zbl 0990.68052
[12] Chern, H.-H.; Hwang, H.-K., Transitional behaviors of the average cost of quicksort with Median-of-(2t+1), Algorithmica, 29, 44-69, (2001) · Zbl 0967.68048
[13] Chern, H.-H.; Hwang, H.-K.; Tsai, T.-H., An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms, J. Algorithms, 44, 177-225, (2002) · Zbl 1030.68114
[14] Darrasse, A.; Hwang, H.-K.; Bodini, O.; Soria, M., Proc. Seventh Workshop on Analytic Algorithmics and Combinatorics: ANALCO, The connectivity-profile of random increasing k-trees, 99-106, (2010), SIAM
[15] Darrasse, A.; Soria, M., IWOCA 2009, Limiting distribution for distances in k-trees, 170-182, (2009), Springer · Zbl 1267.05106
[16] Darrasse, A.; Soria, M., pp., (2012)
[17] Devroye, L.; Janson, S., Long and short paths in uniform random recursive dags, Arkiv för Matematik, 49, 61-77, (2011) · Zbl 1230.60092
[18] Drmota, M., Random Trees, pp., (2009), Springer · Zbl 1170.05022
[19] Drmota, M.; Gittenberger, B., On the profile of random trees, Random Struct. Alg., 10, 421-451, (1997) · Zbl 0882.60084
[20] Drmota, M.; Hwang, H.-K., Bimodality and phase transitions in the profile variance of random binary search trees, SIAM J. Discrete Math., 19, 19-45, (2005) · Zbl 1086.68037
[21] Drmota, M.; Janson, S.; Neininger, R., A functional limit theorem for the profile of search trees, Ann. Appl. Probab., 18, 288-333, (2008) · Zbl 1143.68019
[22] Durrett, R., Random Graph Dynamics, pp., (2006), Cambridge University Press · Zbl 1223.05002
[23] Fisher, M. L., Optimal solution of vehicle routing problems using minimum k-trees, Oper. Res., 42, 626-642, (1994) · Zbl 0815.90066
[24] Flajolet, P.; Odlyzko, A., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 216-240, (1990) · Zbl 0712.05004
[25] Flajolet, P.; Sedgewick, R., Analytic Combinatorics, pp., (2009), Cambridge University Press · Zbl 1165.05001
[26] Frieze, A. M.; Tsourakakis, C. E.; Bonato, A.; Janssen, J. C. M., WAW, On certain properties of random Apollonian networks, 93-112, (2012), Springer · Zbl 1342.05139
[27] Fuchs, M.; Hwang, H.-K.; Neininger, R., Profiles of random trees: limit theorems for random recursive trees and binary search trees, Algorithmica, 46, 367-407, (2006) · Zbl 1106.68083
[28] Gao, Y., The degree distribution of random k-trees, Theoret. Comput. Sci., 410, 688-695, (2009) · Zbl 1162.68024
[29] Greene, D. H., pp., (1983)
[30] Hennequin, P., pp., (1991)
[31] Hwang, H.-K., Asymptotic expansions for the Stirling numbers of the first kind, J. Combin. Theory Ser. A, 71, 343-351, (1995) · Zbl 0833.05005
[32] Hwang, H.-K., Profiles of random trees: plane-oriented recursive trees, Random Struct. Alg., 30, 380-413, (2007) · Zbl 1115.05083
[33] Labelle, G.; Lamathe, C.; Leroux, P., Labelled and unlabelled enumeration of k-gonal 2-trees, J. Combin. Theory Ser. A, 106, 193-219, (2004) · Zbl 1042.05007
[34] Lin, G., An improved approximation algorithm for multicast k-tree routing, J. Combin. Optim., 9, 349-356, (2005) · Zbl 1093.90017
[35] Mahmoud, H. M.; Smythe, R. T.; Szymański, J., On the structure of random plane-oriented recursive trees and their branches, Random Struct. Alg., 4, 151-176, (1993) · Zbl 0773.05040
[36] Marckert, J.-F.; Albenque, M., Some families of increasing planar maps, Electron. J. Probab., 13, 1624-1671, (2008) · Zbl 1192.60019
[37] Martinhon, C.; Lucena, A.; Maculan, N., Stronger K-tree relaxations for the vehicle routing problem, European J. Oper. Res., 158, 56-71, (2004) · Zbl 1061.90023
[38] Meir, A.; Moon, J. W., On the altitude of nodes in random trees, Canad. J. Math., 30, 997-1015, (1978) · Zbl 0394.05015
[39] Morcrette, B., pp., (2010)
[40] Newelski, L.; Rosłanowski, A., The ideal determined by the unsymmetric game, Proc. Amer. Math. Soc., 117, 823-831, (1993) · Zbl 0778.03016
[41] Newman, M. E. J., The structure and function of complex networks, SIAM Rev., 45, 167-256, (2003) · Zbl 1029.68010
[42] Palmer, E. M.; Read, R. C., On the number of plane 2-trees, J. London Math. Soc., 6, 583-592, (1973) · Zbl 0257.05120
[43] Panholzer, A.; Seitz, G.; Drmota, M.; Gittenberger, B., AofA’10, Ordered increasing k-trees: Introduction and analysis of a preferential attachment network model, 549-564, (2010), DMTCS · Zbl 1355.05227
[44] Park, G.; Hwang, H.-K.; Nicodème, P.; Szpankowski, W., Profiles of tries, SIAM J. Comput., 38, 1821-1880, (2009) · Zbl 1191.68898
[45] Pávó, I., Generation of the k-trees of a graph, Acta Cybernet., 1, 57-68, (1971) · Zbl 0221.05055
[46] Prodinger, H.; Urbanek, F. J., On monotone functions of tree structures, Discrete Appl. Math., 5, 223-239, (1983) · Zbl 0508.05042
[47] Proskurowski, A., K-trees: representations and distances, Congr. Numer., 29, 785-794, (1980) · Zbl 0454.05023
[48] Rényi, A., On the number of endpoints of a k-tree, Studia Sci. Math. Hungar., 5, 5-10, (1970) · Zbl 0202.23602
[49] Rose, D. J., On simple characterizations of k-trees, Discrete Math., 7, 317-322, (1974) · Zbl 0285.05128
[50] Stevens, W. R., TCP/IP Illustrated, Traceroute program, pp., (1994), Addison-Wesley Professional
[51] Szymański, J., Random Graphs ’85: Poznań, 1985, On a nonuniform random recursive tree, 297-306, (1987), North-Holland
[52] Viger, F.; Augustin, B.; Cuvellier, X.; Magnien, C.; Latapy, M.; Friedman, T.; Teixeira, R., Detection, understanding, and prevention of traceroute measurement artifacts, Comput. Networks, 52, 998-1018, (2008) · Zbl 1138.68326
[53] Win, S., On a connection between the existence of k-trees and the toughness of a graph, Graphs Combin., 5, 201-205, (1989) · Zbl 0673.05054
[54] Zhang, Z.; Chen, L.; Zhou, S.; Fang, L.; Guan, J.; Zou, T., Analytical solution of average path length for Apollonian networks, Phys. Rev. E, 77, pp., (2008)
[55] Zhang, Z.; Rong, L.; Comellas, F., High-dimensional random Apollonian networks, Phys. A, 364, 610-618, (2006) · Zbl 1086.68017
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.