Data center interconnection networks are not hyperbolic

DOI10.1016/j.tcs.2016.05.025zbMath1344.68173OpenAlexW2404409149MaRDI QIDQ301597

Guillaume Ducoffe, David Coudert

Publication date: 30 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.025

zbMATH Keywords

Cayley graphGromov hyperbolicitydata center interconnection networkgraph endomorphismgreedy routing schememetric embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Network protocols (68M12)

Related Items (7)

On the hyperbolicity of bipartite graphs and intersection graphs ⋮ On the combinatorial design of data centre network topologies ⋮ On the hyperbolicity constant of circular-arc graphs ⋮ A simple approach for lower-bounding the distortion in any hyperbolic embedding ⋮ Using semidirect products of groups to build classes of interconnection networks ⋮ Fault tolerant supergraphs with automorphisms ⋮ Simplified constructions of almost peripheral graphs and improved embeddings into them

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The diameter of the cube-connected cycles
• Bounds on Gromov hyperbolicity constant in graphs
• On the hyperbolicity of random graphs
• Hyperbolicity and chordality of a graph
• A game of cops and robbers
• Mobility of vertex-transitive graphs
• Eccentric graphs
• A survey of the theory of hypercube graphs
• Bounds for sorting by prefix reversal
• Expanders are not hyperbolic
• Vertex-to-vertex pursuit in a graph
• Hyperbolic bridged graphs
• Weakly symmetric graphs and their endomorphism monoids
• Automatic structures, rational growth, and geometrically finite hyperbolic groups
• On embedding trees into uniformly convex Banach spaces
• On the Hyperbolicity of Small-World and Treelike Random Graphs
• On Computing the Gromov Hyperbolicity
• Euclidean versus Hyperbolic Congestion in Idealized versus Experimental Networks
• Cop and Robber Games When the Robber Can Hide and Ride
• Generalized Hypercube and Hyperbus Structures for a Computer Network
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• A group-theoretic model for symmetric interconnection networks
• Broadcasting and Gossiping in de Bruijn Networks
• Transposition networks as a class of fault-tolerant robust networks
• Metric Embedding, Hyperbolic Space, and Social Networks
• Isomorphisms of the De Bruijn digraph and free‐space optical networks
• Finite Transitive Graph Embeddings into a Hyperbolic Metric Space Must Stretch or Squeeze
• Traffic Congestion in Expanders and (p,δ)–Hyperbolic Spaces
• A CLASS OF DATA-CENTER NETWORK MODELS OFFERING SYMMETRY, SCALABILITY, AND RELIABILITY
• To Approximate Treewidth, Use Treelength!
• Self-dual configurations and regular graphs
• On the hyperbolicity of chordal graphs
• Quasi-centers and radius related to some iterated line digraphs, proofs of several conjectures on de Bruijn and Kautz graphs

This page was built for publication: Data center interconnection networks are not hyperbolic