Polynomial and Extensible Solutions in Lock-Chart Solving
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00311856" target="_blank" >RIV/68407700:21230/16:00311856 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1080/08839514.2017.1279110" target="_blank" >http://dx.doi.org/10.1080/08839514.2017.1279110</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1080/08839514.2017.1279110" target="_blank" >10.1080/08839514.2017.1279110</a>
Alternative languages
Result language
angličtina
Original language name
Polynomial and Extensible Solutions in Lock-Chart Solving
Original language description
Lock-chart (also known as master-key system) solving is a process for designing mechanical keys and locks so that every key can open and be blocked in a user-defined set of locks. We present several algorithms as a result of our 3 years industrial collaboration project, chosen by their asymptotic time complexity and extensibility, which is the ability to add new keys and locks and satisfy the previously unforeseen blocking requirements. Our strongest result is a linear-time algorithm to find the largest diagonal lock-chart with a condition on mechanical properties of keys. Without these restrictions, but given a solution for master keys, the problem is translated into a maximum independent set problem and a greedy approximation is proposed. We evaluate the algorithms on a generated dataset using a non-backtracking procedure to simulate minimal extensions. Both approaches are suggested as heuristics or subroutines for a backtracking constraint satisfaction problem-based (CSP) solver.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
20201 - Electrical and electronic engineering
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Applied Artificial Intelligence
ISSN
0883-9514
e-ISSN
1087-6545
Volume of the periodical
30
Issue of the periodical within the volume
10
Country of publishing house
GB - UNITED KINGDOM
Number of pages
19
Pages from-to
923-941
UT code for WoS article
000397335700002
EID of the result in the Scopus database
2-s2.0-85013498051