@InProceedings{Werner-CVWW07,
  IS = { zkontrolovano 13 Dec 2007 },
  UPDATE  = { 2007-07-24 },
  author =     {Tom{\'a}{\v s} Werner and Alexander Shekhovtsov},
  title =      {Unified Framework for Semiring-Based Arc Consistency and 
                Relaxation Labeling},
  booktitle =  {CVWW 2007: Proceedings of the 12th Computer Vision Winter Workshop},
  pages =      {27--34},
  year =       {2007},
  editor =     {Michael Grabner and Helmut Grabner},
  month =      {February},
  publisher =  {Verlag der Technischen Universit{\"a}t Graz},
  address =    {Technikerstr. 4, A-8010, Graz, Austria},
  isbn =       {978-3-902465-60-3},
  book_pages = {156},
  venue =      {St. Lambrecht, Austria},
  annote = {Constraint Satisfaction Problem (CSP), including its soft
    modifications, is ubiquitous in artificial intelligence and
    related fields. In computer vision and pattern recognition, the
    crisp CSP is more known as the consistent labeling problem and
    certain soft CSPs as certain inference problems in Markov Random
    Fields. Many soft CSPs can be seen as special cases of the
    semiring-based CSP (SCSP), using two abstract operations that form
    a semiring.  A fundamental concept to tackle the CSP, as well as
    the SCSPs with idempotent semiring multiplication, are arc
    consistency algorithms, also known as relaxation
    labeling. Attempts have been made to generalize arc consistency
    for soft CSPs with non-idempotent semiring multiplication. We
    achieve such generalization by generalizing max-sum diffusion of
    Kovalevsky and Koval, used to decrease Schlesinger's upper bound
    on the max-sum CSP. We formulate the proposed generalized arc
    consistency in the semiring framework.  Newly, we introduce
    sum-product arc consistency and give its relation to max-sum arc
    consistency and optimal max-sum arc consistency.},
  keywords = {constraint satisfaction and optimisation, arc consistency, 
    Markov random field, undirected graphical model},
  project =    {IST-004176 COSPAL},
  authorship = {60-40},
  psurl = {[PDF]},
}