Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-42432-3_7 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Computational topology,Knot detection and equivalence,SAT and #-SAT solving,Quandle coloring | Algebraic relations,Discrete mathematics,Combinatorics,Algebraic structure,Invariant (mathematics),Knot (unit),Mathematics,Computational topology | Conference |
Volume | ISSN | Citations |
9725 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Fish | 1 | 247 | 22.48 |
| Alexei Lisitsa | 2 | 272 | 45.94 |
| David Stanovský | 3 | 17 | 2.56 |
| Sarah Swartwood | 4 | 0 | 0.34 |