All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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