Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V
89159

23.02.2015

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF]

The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 8.65 and 30. Similarly, the number of spanning trees on S is known to be dn, where the base d lies between 12.52 and 141.07. The fastest known algorithm for counting triangulations of S runs in O(2n) time while that for counting spanning trees on S enumerates them in Ω(12.52n) time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of S and the base of the number of spanning trees of S, respectively, run in time subexponential in n. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of spanning trees on S, respectively.

Last Change: 02/23/15 at 09:11:34
 English
Universität Bonn -> Institut für Informatik -> Abteilung V