Distance Realization Problems with Applications to Internet Tomography

Fan Chung; M. Nahm Garrett; Ronald Graham; David Shallcross

doi:10.1006/jcss.2001.1785

Keywords

HeuristicsRealization (probability)MathematicsUpper and lower boundsGraphConnected componentCombinatoricsOptimization problemComputer scienceDiscrete mathematicsTheoretical computer scienceAlgorithmMathematical optimization

Affiliated Institutions

University of California, San Diego US

Related Publications

Are randomly grown graphs really random?

Duncan S. Callaway , John E. Hopcroft , Jon Kleinberg +2 more

We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined b...

2001 Physical review. E, Statistical physi... 443 citations

The average distances in random graphs with given expected degrees

Fan Chung , Linyuan Lü

Random graph theory is used to examine the “small-world phenomenon”; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain...

2002 Proceedings of the National Academy o... 897 citations

Random graphs with arbitrary degree distributions and their applications

M. E. J. Newman , Steven H. Strogatz , Duncan J. Watts

Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Po...

2001 Physical review. E, Statistical physi... 3631 citations

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

Yu. A. Malkov , D. A. Yashunin

We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed ...

2018 IEEE Transactions on Pattern Analysis... 1341 citations

An algorithm for constructing the aspect graph

William Harry Plantinga , Charles R. Dyer

In this paper we present tight bounds on the maximum size of aspect graphs and give worstcase optimal algorithms for their construction, first in the convex case and then in the...

1986 61 citations

Publication Info

Year: 2001
Type: article
Volume: 63
Issue: 3
Pages: 432-448
Citations: 63
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Distance Realization Problems with Applications to Internet Tomography

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

OpenAlex

Cite This

APA Style

                            
                                
                                    Fan Chung, 
                                
                                    M. Nahm Garrett, 
                                
                                    Ronald Graham
                                
                                et al.
                            
                            (2001). 
                            Distance Realization Problems with Applications to Internet Tomography. 
                            Journal of Computer and System Sciences
                            , 63
                            (3)
                            , 432-448.
                            https://doi.org/10.1006/jcss.2001.1785
                        

Identifiers

DOI: 10.1006/jcss.2001.1785