Meny

Du är här

Computing the Tutte polynomial in vertex-exponential time

Författare:
Publiceringsår: 2008
Språk: Engelska
Sidor: 677-686
Publikation/Tidskrift/Serie: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science
Dokumenttyp: Konferensbidrag
Förlag: IEEE Computer Society

Sammanfattning

The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.

Disputation

Nyckelord

  • Technology and Engineering

Övriga

49th Annual Symposium on Foundations of Computer Science
2008-10-25/2008-10-28
Philadelphia, PA
  • VR
Published
  • Exact algorithms
Yes
  • Algorithms
  • ISSN: 0272-5428

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen