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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom