×

Tree decompositions and social graphs. (English) Zbl 1461.68139

Summary: Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales. Here, we present results from the first detailed empirical evaluation of the use of tree decomposition (TD) heuristics for structure identification and extraction in social graphs. Although TDs have historically been used in structural graph theory and scientific computing, we show that – even with existing TD heuristics developed for those very different areas – TD methods can identify interesting structure in a wide range of realistic informatics graphs. Our main contributions are the following: we show that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; we show that the peripheral bags of these TDs correlate well with low-conductance communities (when they exist) found using local spectral computations; and we show that several types of large-scale “ground-truth” communities, defined by demographic metadata on the nodes of the network, are well-localized in the large-scale and/or peripheral structures of the TDs. Our other main contributions are the following: we provide detailed empirical results for TD heuristics on toy and synthetic networks to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and we prove a theorem providing formal justification for the intuition that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles. Our results suggest future directions for improved TD heuristics that are more appropriate for realistic social graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009. Also available at: arXiv:0810.1355. · Zbl 1205.91144
[2] L. G. S. Jeub, P. Balachandran, M. A. Porter, P. J. Mucha, and M. W. Mahoney. Think locally, act locally: Detection of small, medium-sized, and large communities in large networks. Physical Review E, 91:012821, 2015. · doi:10.1103/PhysRevE.91.012821
[3] A. B. Adcock, B. D. Sullivan, and M. W. Mahoney. Tree-like structure in large social and information networks. In Proc. of the 2013 IEEE ICDM, pages 1-10, 2013.
[4] V. Batagelj and M. Zaversnik. Generalized cores. Technical report. Preprint: arXiv:cs.DS/0202039 (2002). · Zbl 1284.05252
[5] V. Batagelj and M. Zaversnik. An \(O(m)\) algorithm for cores decomposition of networks. Technical report. Preprint: arXiv:cs.DS/0310049 (2003). · Zbl 1284.05252
[6] V. Batagelj and M. Zaversnik. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2):129-145, 2011. · Zbl 1284.05252 · doi:10.1007/s11634-010-0079-y
[7] N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[8] S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23(1):11-24, 1989. · Zbl 0666.68067 · doi:10.1016/0166-218X(89)90031-0
[9] M. W. Bern, E. L. Lawler, and A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs. Journal of Algorithms, 8(2):216-235, 1987. · Zbl 0618.68058 · doi:10.1016/0196-6774(87)90039-3
[10] A. M. C. A. Koster, S. P. M. van Hoesel, and A. W. J. Kolen. Solving partial constraint satisfaction problems with tree decomposition. Networks, pages 170-180, 2002. · Zbl 1027.90072 · doi:10.1002/net.10046
[11] J. Lagergren. Efficient parallel algorithms for graphs of bounded tree-width. Journal of Algorithms, 20(1):20-44, 1996. · Zbl 0840.68058 · doi:10.1006/jagm.1996.0002
[12] I. V. Hicks, A. M. C. A. Koster, and E. Kolotoğlu. Branch and tree decomposition techniques for discrete optimization. TutORials in Operation Research: INFORMS-New\sOrleans, 2005.
[13] J. Zhao, R. L. Malmberg, and L. Cai. Rapid ab initio RNA folding including pseudoknots via graph tree decomposition. In Proceedings of the 6th International Workshop on Algorithms in Bioinformatics, pages 262-273, 2006.
[14] J. Zhao, D. Che, and L. Cai. Comparative pathway annotation with protein-DNA interaction and operon information via graph tree decomposition. In Pacific Symposium on Biocomputing, pages 496-507, 2007.
[15] C. Liu, Y. Song, B. Yan, Y. Xu, and L. Cai. Fast de novo peptide sequencing and spectral alignment via tree decomposition. In Pacific Symposium on Biocomputing, pages 255-266, 2006.
[16] S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society series B, 50:157-224, 1988. · Zbl 0684.68106
[17] D. Karger and N. Srebro. Learning Markov networks: maximum bounded tree-width graphs. In Proceedings of the 12th ACM-SIAM Symposium on Discrete algorithms, pages 392-401, 2001. · Zbl 0987.68067
[18] H. Chen. Quantified constraint satisfaction and bounded treewidth. In Proceedings of the 16th European Conference on Artificial Intelligence, pages 161-165, 2004.
[19] H. L. Bodlaender and R. H. Möhring. The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics, 6(2):181-188, 1993. · Zbl 0773.05091 · doi:10.1137/0406014
[20] C. Chekuri and J. Chuzhoy. Polynomial bounds for the grid-minor theorem. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 60-69, 2014. · Zbl 1315.05131
[21] P.D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217-241, 1994. · Zbl 0799.05057 · doi:10.1007/BF01215352
[22] H. L. Bodlaender and A. M. C. A. Koster. Treewidth computations I. Upper bounds. Inf. Comput., 208(3):259-275, 2010. · Zbl 1186.68328 · doi:10.1016/j.ic.2009.03.008
[23] H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, 1996. · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[24] E. Amir. Approximation algorithms for treewidth. Algorithmica, 56(4):448-479, 2010. · Zbl 1187.68703 · doi:10.1007/s00453-008-9180-4
[25] H. Röhrig. Tree decomposition: a feasibility study. Master’s thesis, Universität des Saarlandes, Saarbrücken, Germany, 1998.
[26] K. Shoikhet and D. Geiger. A practical algorithm for finding optimal triangulations. In Proceedings of AAAI/IAAI, pages 185-190, 1997.
[27] C. Groër, B. D. Sullivan, and D. Weerapurage. INDDGO: Integrated network decomposition & dynamic programming for graph optimization. Technical Report ORNL/TM-2012/176, Oak Ridge National Laboratory, 2012.
[28] B. D. Sullivan et al. Integrated Network Decompositions and Dynamic programming for Graph Optimization (INDDGO), 2012, 2013. http://github.com/bdsullivan/inddgo.
[29] F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X
[30] D. J. Rose and R. E. Tarjan. Algorithmic aspects of vertex elimination. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, pages 245-254, 1975. · Zbl 0382.05049
[31] A. Berry, J. R. S. Blair, and P. Heggernes. Maximum cardinality search for computing minimal triangulations. In Proceeding of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1-12, 2002. · Zbl 1022.68088
[32] A. Berry, J. R. S. Blair, P. Heggernes, and B. W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica, 39(4):287-298, 2004. · Zbl 1090.68080 · doi:10.1007/s00453-004-1084-3
[33] D. Rose, R. Tarjan, and G. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5:266-283, 1976. · Zbl 0353.65019 · doi:10.1137/0205021
[34] R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13:566-579, 1984. · Zbl 0545.68062 · doi:10.1137/0213035
[35] R. E. Tarjan and M. Yannakakis. Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 14(1):254-255, 1985. · Zbl 0562.68055 · doi:10.1137/0214020
[36] A. Becker and D. Geiger. A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence, 125(1-2):3-17, 2001. · Zbl 0972.68152 · doi:10.1016/S0004-3702(00)00075-8
[37] H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, and minimum elimination tree height. Journal of Algorithms, 18:238-255, 1995. · Zbl 0818.68118 · doi:10.1006/jagm.1995.1009
[38] V. Bouchitté, D. Kratsch, H. Müller, and I. Todinca. On treewidth approximations. Discrete Appl. Math., 136(2-3):183-196, 2004. · Zbl 1035.05087 · doi:10.1016/S0166-218X(03)00440-2
[39] B. A. Reed. Finding approximate separators and computing tree width quickly. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 221-228, 1992.
[40] J. A. George. Nested dissection of a regular finite element mesh. SIAM Journal of Numerical Analysis, 10:345-363, 1973. · Zbl 0259.65087 · doi:10.1137/0710032
[41] J. R. Gilbert and R. E. Tarjan. The analysis of a nested dissection algorithm. Numerische Mathematik, 50(4):377-404, 1986. · Zbl 0645.65012 · doi:10.1007/BF01396660
[42] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20:359-392, 1998. · Zbl 0915.68129 · doi:10.1137/S1064827595287997
[43] H. M. Markowitz. The elimination form of the inverse and its application to linear programming. Management Science, 3(3):255-269, 1957. · Zbl 0995.90592 · doi:10.1287/mnsc.3.3.255
[44] P. R. Amestoy, T. A. Davis, and I. S. Duff. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Transactions on Mathematical Software (TOMS), 30(3):381-388, 2004. · Zbl 1070.65534 · doi:10.1145/1024074.1024081
[45] P. R. Amestoy, T. A. Davis, and I. S. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886-905, 1996. · Zbl 0861.65021 · doi:10.1137/S0895479894278952
[46] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. · Zbl 1183.68483
[47] H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1-23, 1993. · Zbl 0804.68101
[48] H. L. Bodlaender. Discovering treewidth. In Proceedings of the 31st international conference on Theory and Practice of Computer Science, pages 1-16, 2005. · Zbl 1117.68451
[49] H. L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Proceeding of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1-14, 2006. · Zbl 1167.68404
[50] H. L. Bodlaender and A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255-269, 2007. · doi:10.1093/comjnl/bxm037
[51] J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In A. George, J. R. Gilbert, and J. W. H. Liu, editors, Graph Theory and Sparse Matrix Computation, The IMA Volumes in Mathematics and its Applications, Volume 56, pages 1-29. Springer-Verlag, 1993. · Zbl 0803.68081 · doi:10.1007/978-1-4613-8369-7_1
[52] E. Amir. Efficient approximation for triangulation of minimum treewidth. In Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, pages 7-15, 2001.
[53] A. M. C. A. Koster, H. L. Bodlaender, and S. P. M. van Hoesel. Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics, 8:54-57, 2001. · Zbl 1409.05176 · doi:10.1016/S1571-0653(05)80078-2
[54] A. Berry, P. Heggernes, and G. Simonet. The minimum degree heuristic and the minimal triangulation process. In H. L. Bodlaender, editor, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, pages 58-70. Springer, 2003. · Zbl 1255.05186 · doi:10.1007/978-3-540-39890-5_6
[55] P. Heggernes. Minimal triangulations of graphs: A survey. Discrete Mathematics, 306(3):297-317, 2006. · Zbl 1086.05069 · doi:10.1016/j.disc.2005.12.003
[56] C. Wang, T. Liu, P. Cui, and K. Xu. A note on treewidth in random graphs. In Proceeding of the 5th International Conference on Combinatorial Optimization and Applications, pages 491-499, 2011. · Zbl 1342.05145
[57] Y. Gao. Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs. Discrete Applied Mathematics, 160(4-5):566-578, 2012. · Zbl 1239.05166 · doi:10.1016/j.dam.2011.10.013
[58] A. B. Adcock, B. D. Sullivan, O. R. Hernandez, and M. W. Mahoney. Evaluating OpenMP tasking at scale for the computation of graph hyperbolicity. In Proc. of the 9th IWOMP, pages 71-83, 2013.
[59] A. B. Adcock. Characterizing, identifying, and using tree-like structure in social and information networks. PhD thesis, Stanford University, 2014.
[60] M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, pages 75-263. Springer, 1987. · Zbl 0634.20015 · doi:10.1007/978-1-4613-9586-7_3
[61] J. M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, H. Shapiro, and H. Short. Notes on word hyperbolic groups. In E. Ghys, A. Haefliger, and A. Verjovski, editors, Group Theory from a Geometrical Viewpoint, ICTP Trieste Italy, pages 3-63. World Scientific, 1991. · Zbl 0849.20023
[62] E. A. Jonckheere, P. Lohsoonthorn, and F. Bonahon. Scaled Gromov hyperbolic graphs. Journal of Graph Theory, 57(2):157-180, 2008. · Zbl 1160.05017 · doi:10.1002/jgt.20275
[63] E. A. Jonckheere, P. Lohsoonthorn, and F. Ariaei. Scaled Gromov four-point condition for network graph curvature computation. Internet Mathematics, 7(3):137-177, 2011. · Zbl 1451.05218
[64] W. Chen, W. Fang, G. Hu, and M. W. Mahoney. On the hyperbolicity of small-world and tree-like random graphs. Internet Mathematics, 9(4):434-491, 2013. Also available at: arXiv:1201.1717. · Zbl 1338.05244
[65] K. Verbeek and S. Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the 30th Annual Symposium on Computational Geometry, pages 501-510, 2014. · Zbl 1395.05048
[66] G. Brinkmann, J. H. Koolen, and V. Moulton. On the hyperbolicity of chordal graphs. Annals of Combinatorics, 5(1):61-69, 2001. · Zbl 0985.05021 · doi:10.1007/s00026-001-8007-7
[67] Y. Wu and C. Zhang. Hyperbolicity and chordality of a graph. The Electronic Journal of Combinatorics, 18(1):P43, 2011. · Zbl 1220.05020
[68] Y. Dourisboure and C. Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008-2029, 2007. · Zbl 1118.05077 · doi:10.1016/j.disc.2005.12.060
[69] D. Lokshtanov. On the complexity of computing treelength. In Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science, pages 276-287, 2007. · Zbl 1147.68535
[70] M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory Series B, 99(1):218-228, 2009. · Zbl 1205.05049 · doi:10.1016/j.jctb.2008.06.004
[71] A. Kosowski, B. Li, N. Nisse, and K. Suchan. \(k\)-chordal graphs: From cops and robber to compact routing via treewidth. In Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming, pages 610-622, 2012. · Zbl 1318.68127
[72] F. F. Dragan. Tree-like structures in graphs: A metric point of view. In Proceeding of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1-4, 2013. · Zbl 1417.05028
[73] M. Abu-Ata and F. F. Dragan. Metric tree-like structures in real-life networks: an empirical study. Networks, 67(1):49-68, 2016. · doi:10.1002/net.21631
[74] M. M. Abu-Ata. Tree-Like Structure in Graphs and Embeddability to Trees. PhD thesis, Kent State University, 2014.
[75] Y. Shavitt and T. Tankel. Hyperbolic embedding of Internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking, 16(1):25-36, 2008. · doi:10.1109/TNET.2007.899021
[76] M. P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha. Core-periphery structure in networks. SIAM Journal on Applied Mathematics, 74(1):167-190, 2014. · Zbl 1368.62169 · doi:10.1137/120881683
[77] S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269-287, 1983. · doi:10.1016/0378-8733(83)90028-X
[78] J. Ignacio Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In Annual Advances in Neural Information Processing Systems 18: Proceedings of the 2005 Conference, pages 41-50, 2006.
[79] J. Ignacio Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani. K-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, 3(2):371-393, 2008. · Zbl 1145.68470 · doi:10.3934/nhm.2008.3.371
[80] J. Healy, J. Janssen, E. Milios, and W. Aiello. Characterization of graphs using degree cores. In WAW ’08: Proceedings of the 6th Workshop on Algorithms and Models for the Web-Graph, pages 137-148, 2008. · Zbl 1142.68313
[81] V. Batagelj and A. Mrvar. Pajek—analysis and visualization of large networks. In Proceedings of Graph Drawing, pages 477-478, 2001. · Zbl 1054.68564
[82] J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive networks. In Proceedings of the 27th IEEE International Conference on Data Engineering, pages 51-62, 2011.
[83] P. Colomer-de Simon, A. Serrano, M. G. Beiro, J. Ignacio Alvarez-Hamelin, and M. Boguna. Deciphering the global organization of clustering in real complex networks. Scientific Reports, 3:2517, 2013. · doi:10.1038/srep02517
[84] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6(11):888-893, 2010. · doi:10.1038/nphys1746
[85] J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. Proceedings of the National Academy of Sciences, 109(16):5962-5966, 2012.
[86] V. Ramasubramanian, D. Malkhi, F. Kuhn, M. Balakrishnan, A. Gupta, and A. Akella. On the treeness of internet latency and bandwidth. In Proceedings of the 2009 ACM SIGMETRICS International Conference on Measurement and modeling of computer systems, pages 61-72, 2009.
[87] F. de Montgolfier, M. Soto, and L. Viennot. Treewidth and hyperbolicity of the internet. In Proceedings of the 10th IEEE International Symposium on Network Computing and Applications (NCA), pages 25-32, 2011.
[88] T. Maehara, T. Akiba, Y. Iwata, and K. Kawarabayashi. Computing personalized PageRank quickly by exploiting graph structures. Proceedings of the VLDB Endowment, 7:1023-1034, 2014.
[89] B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1-2):49-82, 1993. · Zbl 0789.68083 · doi:10.1016/0304-3975(93)90064-Z
[90] A. G. Percus, G. Istrate, B. Goncalves, R. Z. Sumi, and S. Boettcher. The peculiar phase structure of random graph bisection. Journal of Mathematical Physics, 49(12):125219, 2008. · Zbl 1159.81337 · doi:10.1063/1.3043666
[91] F.R.K. Chung and L. Lu. Complex Graphs and Networks, volume 107 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 2006. · Zbl 1114.90071
[92] Supporting website. http://snap.stanford.edu/data/index.html.
[93] A. L. Traud, P. J. Mucha, and M. A. Porter. Social structure of Facebook networks. Physica A, 391:4165-4180, 2012. · doi:10.1016/j.physa.2011.12.021
[94] L.A. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: divided they blog. In LinkKDD ’05: Proceedings of the 3rd International Workshop on Link Discovery, pages 36-43, 2005.
[95] D.J. Watts and S.H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440-442, 1998. · Zbl 1368.05139 · doi:10.1038/30918
[96] E. R. Gansner and S. C. North. An open graph visualization system and its applications to software engineering. Software—Practice and Experience, 30(11):1203-1233, 2000. · Zbl 1147.68782 · doi:10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N
[97] T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software (TOMS), 38(1):1:1-1:25, 2011. · Zbl 1365.65123
[98] T. Malisiewicz. Open source code: Graphviz matlab magic. https://github.com/quantombone/graphviz_matlab_magic, May 2010.
[99] P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17-61, 1960. · Zbl 0103.16301
[100] B. Bollobás. Random Graphs. Academic Press, London, 1985. · Zbl 0567.05042
[101] R. Andersen, F.R.K. Chung, and K. Lang. Local graph partitioning using PageRank vectors. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 475-486, 2006.
[102] R. Diestel and M. Müller. Connected tree-width. Technical report. Preprint: arXiv:arXiv:1211.7353 (2012). · Zbl 1399.05207
[103] F. F. Dragan and I. Lomonosov. On compact and efficient routing in certain graph classes. Discrete Applied Mathematics, 155(11):1458-1470, 2007. · Zbl 1122.68084 · doi:10.1016/j.dam.2007.03.011
[104] V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs. In Proceedings of the 24th Annual Symposium on Computational Geometry, pages 59-68, 2008. · Zbl 1221.68295
[105] F. Reidl and B. Sullivan. Personal communication, 2014.
[106] P. Bellenbaum and R. Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability, and Computing, 11:541-547, 2002. · Zbl 1018.05081 · doi:10.1017/S0963548302005369
[107] A. Georgakopoulos and P. Sprussel. Geodesic topological cycles in locally finite graphs. The Electronic Journal of Combinatorics, 16(1):R144, 2009. · Zbl 1230.05219
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.