DIMACS TR: 96-07

An algorithm for finding many disjoint monochromatic edges in a complete 2-colored geometric graph



Authors: Gyula Karolyi, Janos Pach, Gabor Tardos and Geza Toth

ABSTRACT

We present an $O(n^{\log\log n+2})$-time algorithm for finding $n$ disjoint monochromatic edges in a complete geometric graph of $3n-1$ vertices, where the edges are colored by two colors.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-07.ps.gz
DIMACS Home Page