| Journal: | Computación y sistemas |
| Database: | PERIÓDICA |
| System number: | 000408050 |
| ISSN: | 1405-5546 |
| Authors: | Sagols, Feliú1 Morales Luna, Guillermo1 Buitrón Dámaso, Israel1 |
| Institutions: | 1Instituto Politécnico Nacional, Centro de Investigación y de Estudios Avanzados, Ciudad de México. México |
| Year: | 2016 |
| Season: | Ene-Mar |
| Volumen: | 20 |
| Number: | 1 |
| Pages: | 81-87 |
| Country: | México |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Analítico |
| English abstract | We formally state Skein Problems in Hamiltonian graphs and prove that they are reduced to the Independence Problem in Graph Theory. Skein problems can be widely used in cryptography, particularly, in protocols for message authentication or entities identification. Let G be a Hamiltonian graph. Given a Hamiltonian cycle H, let ΠΠ be a set of pairwise disjoint sub-paths within H, P1=[v11,…,vm1],…,Pk=[v1k,…,vmk]P1=v11,…,vm1,…,Pk=[v1k,…,vmk] where m and k are two positive integers, then the pairs of extreme vertices V={(v11,vm1),…,(v1k,vmk)}V={(v11,vm1),…,(v1k,vmk)} are connected by the paths at ΠΠ without any crossing. Conversely, let us assume that the following problem is posed: given a collection of pairs V it is required to find a collection of pairwise disjoint paths, without any crossing, connecting each pair at V We reduce this last problem to the Independence Problem in Graph Theory. In particular, for the case of the n-dimensional hypercube, we show that the resulting translated instances are not Berge graphs, thus the most common polynomial-time algorithms to solve the translated problem do not apply. We have built a computing system to explicitly generate the resulting graphs of the reduction to the Independence problem. Nevertheless, due to the doubly exponential growth in terms of n of these graphs, the physical computational resources are quickly exhausted |
| Disciplines: | Ciencias de la computación, Matemáticas |
| Keyword: | Programación, Teoría de la computación, Matemáticas puras, Teoría de gráficas, Gráficas hamiltonianas, Problemas NP-hard, Algoritmos, Gráfica hipercubo, Criptografía |
| Keyword: | Computer science, Mathematics, Computer theory, Programming, Pure mathematics, Graph theory, Hamiltonian graphs, NP-hard problems, Algorithms, Hypercube graph, Cryptography |
| Full text: | Texto completo (Ver PDF) |
