Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case

Noga Alon, Alan Frieze, Dominic Welsh

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

The Tutte‐Gröthendieck polynomial T(G; x, y) of a graph G encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the (x, y) plane give the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper k‐colorings, the (all terminal) reliability probability of the graph, and various other invariants the exact computation of each of which is well known to be #P‐hard. Here we develop a general technique that supplies fully polynomial randomised approximation schemes for approximating the value of T(G; x, y) for any dense graph G, that is, any graph on n vertices whose minimum.

Original languageEnglish (US)
Pages (from-to)459-478
Number of pages20
JournalRandom Structures & Algorithms
Volume6
Issue number4
DOIs
StatePublished - Jul 1995

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case'. Together they form a unique fingerprint.

  • Cite this