A QPTAS for the base of the number of crossing-free structures on a planar point set

Theoretical Computer Science - Tập 711 - Trang 56-65 - 2018
Marek Karpinski1, Andrzej Lingas2, Dzmitry Sledneu3
1Department of Computer Science, University of Bonn, Bonn, Germany
2Department of Computer Science, Lund University, Lund, Sweden
3Centre for Mathematical Sciences, Lund University, Lund, Sweden

Tài liệu tham khảo

Adamaszek, 2014, A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices Alvarez, 2015, Counting triangulations and other crossing-free structures approximately, Comput. Geom., 48, 386, 10.1016/j.comgeo.2014.12.006 Alvarez, 2012, Counting crossing-free structures Alvarez, 2013, A simple aggregative algorithm for counting triangulations of planar point sets and related problems García, 2000, Lower bounds on the number of crossing-free subgraphs of Kn, Comput. Geom., 16, 211, 10.1016/S0925-7721(00)00010-9 Flajolet, 1999, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203, 10.1016/S0012-365X(98)00372-0 Har-Peled, 2014, Quasi-polynomial time approximation scheme for sparse subsets of polygons Hoffmann, 2011, Counting plane graphs: flippability and its applications Marx, 2016, Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems Miller, 1986, Finding small simple cycle separators for 2-connected planar graphs, J. Comput. System Sci., 32, 265, 10.1016/0022-0000(86)90030-9 Sharir, 2011, Counting triangulations of planar point sets, Electron. J. Combin., 18, 10.37236/557 Sharir, 2011, On degrees in random triangulations of point sets, J. Combin. Theory Ser. A, 118, 1979, 10.1016/j.jcta.2011.04.002 Sharir, 2013, Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique, J. Combin. Theory Ser. A, 120, 777, 10.1016/j.jcta.2013.01.002 Sharir, 2006, On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput., 36, 695, 10.1137/050636036 Sibson, 1978, Locally equiangular triangulations, Comput. J., 21, 243, 10.1093/comjnl/21.3.243 Wettstein, 2014, Counting and enumerating crossing-free geometric graphs