Nacionalni portal odprte znanosti

Let ▫$G$▫ be an intersection graph of ▫$n$▫ geometric objects in the plane. We show that a maximum matching in ▫$G$▫ can be found in ▫$O(\rho^{3\omega/2}n^{\omega/2})$▫ time with high probability, where ▫$\rho$▫ is the density of the geometric objects and ▫$\omega>2$▫ is a constant such that ▫$n \ti ...

In the longest plane spanning tree problem, we are given a finite planar point set ▫${\mathcal P}$▫, and our task is to find a plane (i.e., noncrossing) spanning tree for ▫${\mathcal P}$▫ with maximum total Euclidean edge length. Despite more than two decades of research, it remains open whether thi ...