1995/07/01 by Noga Alon, Alan Frieze, Dominic Welsh · 3 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Graph theory and applications #Advanced Combinatorial Mathematics #Tutte polynomial #Mathematics #Combinatorics #Polynomial #Discrete mathematics #Mathematical analysis #Graph
paper · doi:10.1002/rsa.3240060409
openalex publication_date 1995/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/23
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.