On certain connectivity properties of the internet topology

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

Amin Saberi, Christos H. Papadimitriou, 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

InternetRandom graphsScale-free networksConductanceFrugality

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The Small Community Phenomenon in Networks: Models, Algorithms and Applications, Fault tolerant mechanism design, The cover time of the preferential attachment graph, Giant descendant trees, matchings, and independent sets in age-biased attachment graphs, Approximability of the vertex cover problem in power-law graphs, Multiple random walks on graphs: mixing few to cover many, Locality of random digraphs on expanders, Large deviations for the degree structure in preferential attachment schemes, First-passage percolation on a ladder graph, and the path cost in a VCG auction, A Geometric Preferential Attachment Model of Networks II, Rumor spreading in social networks, Unnamed Item, How much can taxes help selfish routing?, Message survival and decision dynamics in a class of reactive complex systems subject to external fields, Parallelism in simulation and modeling of scale-free complex networks, A Theory of Network Security: Principles of Natural Selection and Combinatorics, Unnamed Item, Braess's paradox in expanders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• [https://portal.mardi4nfdi.de/wiki/Publication:4337503 Open problems of Paul Erd�s in graph theory]
• 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