@Article{Flach:TPAMI2013,
  IS = { zkontrolovano 16 Aug 2013 },
  UPDATE  = { 2013-08-16 },
  author =     {Boris Flach},
  title =      {A Class of Random Fields on Complete Graphs with
Tractable Partition Function},
  year =       {2013},
  month =      {September},
  pages =      {2304-2306},
  journal =    {IEEE Transactions on Pattern Analysis and Machine
                  Intelligence},
  publisher =  {IEEE Computer Society},
  address =    {Los Alamitos, CA 90720, USA},
  issn =       {0162-8828},
  volume =     {35},
  number =     {9},
  annote =     {The aim of this short note is to draw attention to a method by
which the partition function and marginal probabilities for a certain class of
random fields on complete graphs can be computed in polynomial time. This class
includes Ising models with homogeneous pairwise potentials but arbitrary
(inhomogeneous) unary potentials. Similarly, the partition function and marginal
probabilities can be computed in polynomial time for random fields on complete
bipartite graphs, provided they have homogeneous pairwise potentials. We expect
that these tractable classes of large scale random fields can be very useful
for the evaluation of approximation algorithms by providing exact error
estimates.},
  keywords =   {approximation theory;computational complexity;graph
theory;probability;approximation algorithm;complete bipartite graph;error
estimation;homogeneous pairwise potential;marginal probability;polynomial time
complexity;random field;tractable partition function;Markov random fields},
  project =    {GAP202/12/2071},
  doi =        {10.1109/TPAMI.2013.99},
}