Institut für Informatik
 
Abteilung V

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

13.05.2017

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set (revised version)
Marek Karpinski, Andrzej Lingas, 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 2.43 and 30 . Similarly, the number of crossing-free spanning trees on S is known to be d^n , where the base d lies between 6.75 and 141.07 . The fastest known algorithm for counting triangulations of S runs in O^∗ (2^n) time while that for counting crossing-free spanning trees runs in O^∗ (7.125^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 crossing-free 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 crossing-free spanning trees on S , respectively.

Last Change: 08/07/17 at 15:15:45
 English
Universität Bonn -> Institut für Informatik -> Abteilung V