Papers by Keyword: Backtracking

Abstract: By improving and extended Kruskal algorithm and using the backtracking method, we obtain an algorithm to find the first k spanning trees with minimum weights. Experiments show that for various types of randomly generated undirected connected graphs of which the number of nodes is 10,000, while the number of edges can be up to millions, this algorithm can obtain results within a few seconds.

Abstract: Internet has become as a social infrastructure. The current Internet architecture based on TCP/IP is faced with many challenges. This fact makes the clean slate design of future Internet architecture represented by ICN (Information-Centric Networking) be a hot research topic. In this paper, a novel routing scheme for ICN (Information-Centric Networking) is proposed. On the basis of name-based routing, a process was designed to look for other available interface through which the backtracking-condition-met interest packet will be forwarded, which can reduce the network blocking rate. Moreover, FIB (Forwarding Information Base) of neighbor nodes will be modified when data packets go through a router, which can realize the efficient use of cache. Also, a concept of "popularity" is introduced to improve CS (Content Store) hit rate. The proposed routing scheme is implemented on NSFNET by simulation, and the experimental results have shown that it is feasible and effective.

Abstract: The problem of anti-collision tag is a common problem of the radio frequency identification (RFID) system. ALOHA algorithm and binary search algorithm is the main algorithm to solve the collision problem. This paper analyzes the effectiveness of binary searching of backtracking algorithm in time slot number of shortening identification tags. Combining the theoretical analysis what needs to be improved in binary searching of backtracking algorithm.

Abstract: This paper presents a greedy search placement algorithm which incorporates backtracking for the leather stock cutting problem. In the leather manufacturing industry the efficient cutting of component parts (stencils) form a hide is of prime importance to maintain profitability. Consequently, the development of new approaches for generating cut-plans that minimise material waste and which can handle problem constraints have practical value. The unique feature of the greedy placement algorithm method presented in this paper is that it incorporates backtracking which allows previous placement steps to be retraced in situations where no placement solution can be found. The underlying encoding method is based on the use of the no-fit polygon (NFP) which describes the boundary around a stencil shape such that a second stencil shape can be placed while just touching the first but without overlapping. A material coverage of 64% can be achieved when taking placement constraints into account.