liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Constructing Algorithms for Constraint Satisfaction and Related Problems: Methods and Applications
Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
2005 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use.

The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e < d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm.

The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution.

Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2005. , 171 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 947
Keyword [en]
constraint satisfaction, CSP, graph problems, algorithm construction, computational complexity, microstructures, graph colouring, decision problems, optimisation problems, quantum computing, molecular computing
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-3836ISBN: 91-85297-99-2 (print)OAI: oai:DiVA.org:liu-3836DiVA: diva2:20454
Public defence
2005-06-03, Visionen, Hus B, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2005-09-20 Created: 2005-09-20 Last updated: 2009-02-12

Open Access in DiVA

fulltext(1243 kB)1409 downloads
File information
File name FULLTEXT01.pdfFile size 1243 kBChecksum SHA-1
c040c33586ee57d564b847fbdff8eceb01b8fcd4845f766986e7e3c43c1703a20b265b55
Type fulltextMimetype application/pdf

Authority records BETA

Angelsmark, Ola

Search in DiVA

By author/editor
Angelsmark, Ola
By organisation
TCSLABThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1409 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1575 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf