文章基本信息

标题：Trajectory Graphs Appearing from the Skein Problems at the Hypercube
本地全文：下载
作者：Feliú Salgols ; Guillermo Morales-Luna ; Israel Buitrón-Dámaso 等
期刊名称：Computación y Sistemas
印刷版ISSN：1405-5546
出版年度：2016
卷号：20
期号：1
页码：81-87
语种：English
出版社：Instituto Politécnico Nacional
其他摘要：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 II be a set of pairwise disjoint sub-paths within H , P 1 = [ v 11 , : : : , v m 1 ], : : : , P k = [ v 1 k , : : : , v mk ] where m and k are two positive integers, then the pairs of extreme vertices V = f ( v 11 , v m 1 ), : : : , ( v 1 k , v mk ) g are connected by the paths at II 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.
其他关键词：Independence problem in graph theory; Berge graphs; doubly-exponential growth.