Premium
The random bipartite nearest neighbor graphs
Author(s) -
Pittel Boris,
Weishaar Robert S.
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199910/12)15:3/4<279::aid-rsa6>3.0.co;2-j
Subject(s) - bipartite graph , combinatorics , limiting , matching (statistics) , k nearest neighbors algorithm , mathematics , random graph , discrete mathematics , graph , statistics , computer science , mechanical engineering , artificial intelligence , engineering
Abstract The bipartite k th nearest neighbor graphs B k are studied. It is shown that B 1 has a limiting expected matching number of approximately 80% of its vertices, that with high probability (whp) B 2 has at least 2 log n /13 log log n vertices not matched, and that whp B 3 does have a perfect matching. We also find a formula for the limiting probability that B 2 is connected and show that whp B 3 is connected. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 279–310, 1999