On certain connectivity properties of the internet topology
From MaRDI portal
Publication:2490261
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
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (18)
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
This page was built for publication: On certain connectivity properties of the internet topology