József Balogh ; Boris Pittel ; Gelasio Salazar - Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle

dmtcs:3366 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3366
Near―perfect non-crossing harmonic matchings in randomly labeled points on a circleArticle

Authors: József Balogh 1; Boris Pittel 1; Gelasio Salazar 2

  • 1 Department of Mathematics [Colombus]
  • 2 Instituto de Fisica [Mexico]

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)$.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: harmonic graph,noncrossing,harmonious labeling,Graceful,convex position,matching,average case behavior,algorithm,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
Funding:
    Source : OpenAIRE Graph
  • Random Combinatorial Structures; Funder: National Science Foundation; Code: 0406024
  • Extremal Graph Theory and Bootstrap Percolation; Funder: National Science Foundation; Code: 0302804

1 Document citing this article

Consultation statistics

This page has been seen 201 times.
This article's PDF has been downloaded 168 times.