Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set

In English

Författare

Summary, in English

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 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 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 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.

Avdelning/ar

Publiceringsår

2015

Språk

Engelska

Sidor

785-796

Publikation/Tidskrift/Serie

Automata, Languages, and Programming/Lecture notes in computer science

Volym

9134

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • Counting spanning trees of a planar point set
  • Counting triangulations of a planar point set
  • Approximation algorithms
  • Computational geometry

Conference name

42nd International Colloquium, ICALP 2015

Conference date

2015-07-06 - 2015-07-10

Conference place

Kyoto, Japan

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-662-47671-0