
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 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 CrossingFree 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 c^{n}, where the base c lies between 8.65 and 30. Similarly, the number of spanning trees on S is known to be d^{n}, where the base d lies between 12.52 and 141.07. The fastest known algorithm for counting triangulations of S runs in O^{∗}(2^{n}) time while that for counting spanning trees on S enumerates them in Ω(12.52^{n}) 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 quasipolynomial 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 