Geodesic
Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

Consider a set $S$ of points in the plane in convex position, where each point has an integer label from $\{0,1,\ldots,n-1\}$. This naturally induces a labeling of the edges: each edge $(i,j)$ is assigned label $i+j$, modulo $n$. We propose the algorithms for finding large non―crossing $\textit{harmonic}$ matchings or paths, i. e. the matchings or paths in which no two edges have the same label. When the point labels are chosen uniformly at random, and independently of each other, our matching algorithm with high probability (w.h.p.) delivers a nearly―perfect matching, a matching of size $n/2 - O(n^{1/3}\ln n)$. 
@article{DMTCS_2005_special_249_a14,
     author = {Balogh, J\'ozsef and Pittel, Boris and Salazar, Gelasio},
     title = {Near{\textemdash}perfect non-crossing harmonic matchings in randomly labeled points on a circle},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3366},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3366/}
}
TY  - JOUR
AU  - Balogh, József
AU  - Pittel, Boris
AU  - Salazar, Gelasio
TI  - Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3366/
DO  - 10.46298/dmtcs.3366
LA  - en
ID  - DMTCS_2005_special_249_a14
ER  - 
%0 Journal Article
%A Balogh, József
%A Pittel, Boris
%A Salazar, Gelasio
%T Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3366/
%R 10.46298/dmtcs.3366
%G en
%F DMTCS_2005_special_249_a14
Balogh, József; Pittel, Boris; Salazar, Gelasio. Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3366. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3366/

Cité par Sources :