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 and Lower Bounds on the Time Complexity of Infinite-domain CSPs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
2015 (English)In: Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings / [ed] Pesant, Gilles, Springer Berlin/Heidelberg, 2015, Vol. 9255, p. 183-199Conference paper, Published paper (Refereed)
Abstract [en]

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. Vol. 9255, p. 183-199
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9255
National Category
Computer and Information Sciences Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-123120DOI: 10.1007/978-3-319-23219-5_14ISI: 000364707100014ISBN: 978-3-319-23218-8 (print)OAI: oai:DiVA.org:liu-123120DiVA, id: diva2:876689
Conference
21st International Conference on Principles and Practice of Constraint Programming (CP-2015)
Available from: 2015-12-04 Created: 2015-12-04 Last updated: 2018-02-20

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterLagerkvist, Victor

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, Victor
By organisation
Software and SystemsFaculty of Science & Engineering
Computer and Information SciencesComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 38 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