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
Upper Bounds on the Time Complexity of Temporal CSPs
Linköping University, Department of Computer and Information Science.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The temporal constraint satisfaction problem (CSP) offers a formalized way to reason about in which order tasks should be accomplished. Using this we can model a wide set of specific problems from scheduling to AI. In this thesis we present two algorithms, Algorithm A and Algorithm B, to solve temporal CSPs focused on improving the worst case time complexity. The first algorithm solves temporal CSPs by an exhaustive search of all weak orderings. The time complexity is in , thus within a polynomial factor of the corresponding Ordered Bell Number. We also show that it can solve CSP in Allen’s algebra within a polynomial factor of the corresponding number of relations between intervals on a line, thus in   time. The second algorithm also solves temporal CSPs but where the constraints have a bounded number of disjuncts. It will assume some order and then make a backtracking search guided by the constraints. In this case the time complexity will be in . Finally we will show that this also improves the time complexity of CSP in Allen’s to .

Place, publisher, year, edition, pages
2016. , 24 p.
Keyword [en]
CSP, Algorithms
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-129778ISRN: LIU-IDA/LITH-EX-A--16/022--SEOAI: oai:DiVA.org:liu-129778DiVA: diva2:943554
Subject / course
Computer Engineering
Presentation
2016-06-09, 09:25 (Swedish)
Supervisors
Examiners
Available from: 2016-06-29 Created: 2016-06-28 Last updated: 2016-06-29Bibliographically approved

Open Access in DiVA

fulltext(327 kB)129 downloads
File information
File name FULLTEXT01.pdfFile size 327 kBChecksum SHA-512
7ad4488e9eeb1d52cdefc37fe2daf7f2e353fd64865a0e61e06591d627e94cfa09c540db1ea14def174c20a62f7dc1b19cdf4c458d830149fdfa3a42c2f94985
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Stockman, Peter
By organisation
Department of Computer and Information Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 129 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

urn-nbn

Altmetric score

urn-nbn
Total: 919 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