uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • 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
Tractable symmetry breaking for CSPs with interchangeable values.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD. (ASTRA)
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS. (ASTRA)
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. CSD. (ASTRA)
2003 (English)In: Proceedings of the eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003), 2003, 277-282 p.Conference paper, Published paper (Refereed)
Abstract [en]

Symmetry breaking in CSPs has attracted consid­erable attention in recent years. Various general schemes have been proposed to eliminate sym­metries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This paper studies classes of CSPs for which symmetry breaking is tractable. It identifies several CSP classes which feature var­ious forms of value interchangeability and shows that symmetry breaking can be performed in con­stant time and space during search using dedicated search procedures. Experimental results also show the benefits of symmetry breaking on these CSPs, which encompass many practical applications.

Place, publisher, year, edition, pages
2003. 277-282 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-48199OAI: oai:DiVA.org:uu-48199DiVA: diva2:76105
Available from: 2007-02-15 Created: 2007-02-15

Open Access in DiVA

No full text

Other links

http://www.it.uu.se/research/group/astra/publications/IJCAI03.ps

Authority records BETA

Flener, PierrePearson, JustinÅgren, Magnus

Search in DiVA

By author/editor
Flener, PierrePearson, JustinÅgren, Magnus
By organisation
Department of Information TechnologyComputing ScienceComputer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 329 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • 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