Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331268" target="_blank" >RIV/00216208:11320/16:10331268 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-42432-3_7" target="_blank" >http://dx.doi.org/10.1007/978-3-319-42432-3_7</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-42432-3_7" target="_blank" >10.1007/978-3-319-42432-3_7</a>

Result language
angličtina
Original language name
Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT
Original language description
We apply SAT and #-SAT to problems of computational topology: knot detection and recognition. Quandle coloring can be viewed as associations of elements of algebraic structures, called quandles, to arcs of knot diagrams such that certain algebraic relations hold at each crossing. The existence of a coloring (called colorability) and the number of colorings of a knot by a quandle are knot invariants that can be used to distinguish knots. We realise coloring instances as SAT and #-SAT instances, and produce experimental data demonstrating that a SAT-based approach to colorability is a practically efficient method for knot detection and #-SAT can be utilised for knot recognition.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA13-01832S" target="_blank" >GA13-01832S: General algebra and its connections to computer science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)