On certain connectivity properties of the internet topology

DOI10.1016/j.jcss.2005.06.009zbMath1090.68002MaRDI QIDQ2490261

Christos H. Papadimitriou, Amin Saberi, Milena Mihail

Publication date: 28 April 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.06.009

zbMATH Keywords

Internet; Random graphs; Scale-free networks; Conductance; Frugality

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

Related Items

A Geometric Preferential Attachment Model of Networks II, Approximability of the vertex cover problem in power-law graphs, Rumor spreading in social networks, The cover time of the preferential attachment graph, Parallelism in simulation and modeling of scale-free complex networks, Large deviations for the degree structure in preferential attachment schemes, Fault tolerant mechanism design, How much can taxes help selfish routing?, Unnamed Item, The Small Community Phenomenon in Networks: Models, Algorithms and Applications, First-passage percolation on a ladder graph, and the path cost in a VCG auction, Braess's paradox in expanders

Cites Work

• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Bounds on the cover time
• The diameter of random regular graphs
• The degree sequence of a scale-free random graph process
• A Random Graph Model for Power Law Graphs
• Algorithmic mechanism design (extended abstract)
• Emergence of Scaling in Random Networks
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Crawling on web graphs
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• The Spectra of Random Graphs with Given Expected Degrees
• Paths in graphs
• A BGP-based mechanism for lowest-cost routing
• Algorithms, games, and the internet
• The average distances in random graphs with given expected degrees
• The diameter of sparse random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item