SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:lup.lub.lu.se:17fb22d9-b283-4a4b-8bc2-2b820ef32144"
 

Sökning: onr:"swepub:oai:lup.lub.lu.se:17fb22d9-b283-4a4b-8bc2-2b820ef32144" > Computing the Tutte...

Computing the Tutte polynomial in vertex-exponential time

Björklund, Andreas (författare)
Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
Husfeldt, Thore (författare)
Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
Kaski, Petteri (författare)
visa fler...
Koivisto, Mikko (författare)
visa färre...
 (creator_code:org_t)
2008
2008
Engelska.
Ingår i: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 677-686
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Publikations- och innehållstyp

kon (ämneskategori)
ref (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy