Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.     

Block cipher based on reversible cellular automata

We propose a new encryption algorithm relying on reversible cellular automata (CA). The behavior complexity of CA and their parallel nature makes them interesting candidates for cryptography. The proposed algorithm belongs to the class of symmetric key systems. Marcin Seredynski: He is a Ph.D. student at University of Luxembourg and Polish Academy of Sciences. He received his M.S. in 2004 from Faculty of Electronics and Information Technology in Warsaw University of Technology. His research interests include cryptography, cellular automata, nature inspired algorithms and network security. Currently he is working on intrusion detection algorithms for ad-hoc networks. Pascal Bouvry, Ph.D.: He earned his undergraduate degree in Economical & Social Sciences and his Master degree in Computer Science with distinction (’91) from the University of Namur, Belgium. He went on to obtain his Ph.D. degree (’94) in Computer Science with great distinction at the University of Grenoble (INPG), France. His research at the IMAG laboratory focussed on Mapping and scheduling task graphs onto Distributed Memory Parallel Computers. Next, he performed post-doctoral researches on coordination languages and multi-agent evolutionary computing at CWI in Amsterdam. He gained industrial experience as manager of the technology consultant team for FICS in the banking sector (Brussels, Belgium). Next, he worked as CEO and CTO of SDC (Ho Chi Minh city, Vietnam) in the telecom, semi-conductor and space industry. After that, He moved to Montreal Canada as VP Production of Lat45 and Development Director for MetaSolv Software in the telecom industry. He is currently serving as Professor in the group of Computer Science and Communications (CSC) of the Faculty of Sciences, Technology and Communications of Luxembourg University and he is heading the Intelligent & Adaptive Systems lab. His current research interests include: ad-hoc networks & grid-computing, evolutionary algorithms and multi-agent systems.     

New Results in Minimum-Comparison Sorting

We prove that sorting 13, 14 and 22 elements requires 34, 38 and 71 comparisons, respectively. This solves a long-standing problem posed by Knuth in his famous book The Art of Computer Programming, Volume 3, Sorting and Searching. The results are due to an efficient implementation of an algorithm for counting linear extensions of a given partial order. We also present some useful heuristics which allow us to decrease the running time of the implementation.     

Rigorous Numerical Approach to Isolation in Dynamical Systems on the Example of the Kuramoto-Sivashinsky Equation

This paper describes a method of rigorous verification of an isolating neighborhood based on computer assisted computations. As an application we study the Kuramoto-Sivashinsky equation. The result of the computer assisted proof was directly used in [9] to prove the existence of heteroclinic solutions of the Kuramoto-Sivashinsky equation.     

The VFO-Driven Motion Planning and Feedback Control in Polygonal Worlds for a Unicycle with Bounded Curvature of Motion

Integrated motion planning and control for the purposes of maneuvering mobile robots under state- and input constraints is a problem of vital practical importance in applications of mobile robots such as autonomous transportation. Those constraints arise naturally in practice due to specifics of robot mechanical construction and the presence of obstacles in motion environment. In contrast to approaches focusing on feedback control design under the assumption of given reference motion or motion planning with neglection of subsequent feedback motion execution, we adopt a controller-driven motion planning paradigm, which has recently gained attention of many researchers. It postulates design of motion planning algorithms dedicated to specific feedback control policies, which compute a sequence of feedback control subtasks instead of classically planned open-loop controls or parametric paths. In this spirit, we propose a motion planning algorithm driven by the VFO (Vector Field Orientation) control law for the waypoint-following task. Presented analysis of the VFO control law reveals its beneficial properties, which are subsequently utilized to solve a generally nonlinear and non-convex optimal motion planning problem by formulating it as a mixed-integer linear program (MILP). The solution proposed in this paper yields a waypoint sequence, which is designed for execution by application of the VFO control law to drive a robot to a prescribed final configuration under an input constraint imposed by bounded curvature of robot motion and state constraints resulting from a convex decomposition of task space. Satisfaction of these constraints is guaranteed analytically and exactly, i.e., without utilization of numerical approximations. Moreover, for a given discrete set of possible waypoint orientations, the proposed algorithm computes plans optimal w.r.t. given cost functional, which can be any convex linear combination of quantities such as robot path length, curvature of robot motion, distance to imposed state constraints, etc. Furthermore, the planning algorithm exploits the possibility of both forward or backward movement of the robot to allow maneuvering in demanding environments. Generated waypoint sequences are a compact representation of a motion plan, which can be immediately executed with the VFO controller without any additional post-processing. Validity of the proposed approach has been confirmed by simulation studies and experimental motion execution with a laboratory-scale mobile robot.     

A quadratic boundedness approach to a neural network-based simultaneous estimation of actuator and sensor faults

Neural Computing and Applications - The paper is devoted to the problem of a neural network-based robust simultaneous actuator and sensor faults estimator design for the purpose of the fault...