Search

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

In 1994, Klapper and Goresky (Proceedings of the 1993 Cambridge Security Workshop, Lecture Notes in Computer Science, vol 809, Cambridge, pp 174–178, 1994) proposed a new device called feedback with carry shift register to generate pseudo-random sequences instead of using the traditional device linear feedback shift register. They raised an algorithm called as rational approximation algorithm to recover the device for a given sequence (Klapper and Goresky, Advances in Cryptology, Crypto'95, Lecture Notes in Computer Science, vol 963, Springer, Berlin, pp 262–274, 1995). In this paper, we propose a new algorithm by introducing a new parameter and get the best rational approximation of the sequence much more quickly, especially when the size of the sequence increases dramatically. Unlike most of known algorithms, we can solve the minimal lattice basis instead of one shortest vector. Besides, we can prove that the solution of each step is optimal regardless of the length of the input sequence theoretically. [ABSTRACT FROM AUTHOR]

Boolean functions satisfying good cryptographic criteria when restricted to the set of vectors with constant Hamming weight play an important role in the recent FLIP stream cipher (Méaux et al.: in Lecture Notes in Computer Science, vol. 9665, pp. 311–343, Springer, Berlin, 2016). In this paper, we propose a large class of weightwise perfectly balanced (WPB) functions, which is 2-rotation symmetric. This new class of WPB functions is not extended affinely equivalent to the known constructions. We also discuss the weightwise nonlinearity profile of these functions, and present general lower bounds on k-weightwise nonlinearity, where k is a power of 2. Moreover, we exhibit a subclass of the family. By a recursive lower bound, we show that these subclass of WPB functions have very high weightwise nonlinearity profile. [ABSTRACT FROM AUTHOR]

Diversification-based learning (DBL) derives from a collection of principles and methods introduced in the field of metaheuristics that have broad applications in computing and optimization. We show that the DBL framework goes significantly beyond that of the more recent opposition-based learning (OBL) framework introduced in Tizhoosh (in: Proceedings of international conference on computational intelligence for modelling, control and automation, and international conference on intelligent agents, web technologies and internet commerce (CIMCA/IAWTIC-2005), pp 695–701, 2005), which has become the focus of numerous research initiatives in machine learning and metaheuristic optimization. We unify and extend earlier proposals in metaheuristic search (Glover, in Hao J-K, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Artificial evolution, Lecture notes in computer science, Springer, Berlin, vol 1363, pp 13–54, 1997; Glover and Laguna Tabu search, Springer, Berlin, 1997) to give a collection of approaches that are more flexible and comprehensive than OBL for creating intensification and diversification strategies in metaheuristic search. We also describe potential applications of DBL to various subfields of machine learning and optimization. [ABSTRACT FROM AUTHOR]

By generalizing and completing the work initiated by Stefanutti and Albert (2003, Journal of Universal Computer Science, 9, 1455), this article provides the mathematical foundations of a theoretical approach whose primary goal is to construct a bridge between problem solving, as initially conceived by Newell and Simon (1972, Human problem solving. Englewood Cliffs, NJ: Prentice‐Hall.), and knowledge assessment (Doignon and Falmagne, 1985, International Journal of Man‐Machine Studies, 23, 175; Doignon and Falmagne, 1999, Knowledge spaces. Berlin, Germany: Springer‐Verlag.; Falmagne et al., 2013, Knowledge spaces: Applications in education. New York, NY: Springer‐Verlag; Falmagne and Doignon, 2011, Learning spaces: Interdisciplinary applied mathematics. Berlin, Germany: Springer‐Verlag.). It is shown that the collection of all possible knowledge states for a given problem space is a learning space. An algorithm for deriving a learning space from a problem space is illustrated. As an example, the algorithm is used to derive the learning space of a neuropsychological test whose problem space is well known: the Tower of London (TOL; Shallice, 1982, Philosophical Transactions of the Royal Society of London B: Biological Sciences, 298, 199). The derived learning space could then be used for adaptively assessing individual planning skills with the TOL. [ABSTRACT FROM AUTHOR]