liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Building tractable disjunctive constraints
University of London.
University of Oxford.
Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
Technical Unversity of Crete.
2000 (engelsk)Inngår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 47, nr 5, s. 826-853Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

sted, utgiver, år, opplag, sider
2000. Vol. 47, nr 5, s. 826-853
Emneord [en]
algorithms, theory, complexity, constraint satisfaction problem, disjunctive constraints, independence, NP-completeness, relations
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-49462DOI: 10.1145/355483.355485OAI: oai:DiVA.org:liu-49462DiVA, id: diva2:270358
Tilgjengelig fra: 2009-10-11 Laget: 2009-10-11 Sist oppdatert: 2017-12-12

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Jonsson, Peter

Søk i DiVA

Av forfatter/redaktør
Jonsson, Peter
Av organisasjonen
I samme tidsskrift
Journal of the ACM

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 59 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf