Bodlaender H.L.,University Utrecht |
Fomin F.V.,University of Bergen |
Koster A.M.C.A.,RWTH Aachen |
Kratsch D.,Lita Inc |
Thilikos D.M.,National and Kapodistrian University of Athens
Theory of Computing Systems | Year: 2012
In this note, we give a proof that several vertex ordering problems can be solved in O*(2n) time and O*(2n) space, or in O*(4n) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196-210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486-502, 1987). We survey a number of vertex ordering problems to which the results apply. © 2011 The Author(s).
Ayed H.,CRP Henri Tudor |
Ayed H.,Lita Inc |
Galvez-Fernandez C.,CRP Henri Tudor |
Habbas Z.,Lita Inc |
Khadraoui D.,CRP Henri Tudor
Computers and Industrial Engineering | Year: 2011
In this paper we present an hybrid approach for solving the time-dependent multimodal transport problem. This approach has been tested on realistic instances of the problem providing an adequate balance between computation time and memory space. This solution can be applied to real transport networks in order to reduce the impact of traffic congestion on pollution, economy, and citizen's welfare. A comparison with two previous approaches are given from theoretical point of view as well as experimental performance. © 2010 Elsevier Ltd. All rights reserved.
Couturier J.-F.,Lita Inc |
Heggernes P.,University of Bergen |
Van't Hof P.,University of Bergen |
Kratsch D.,Lita Inc
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2012
The maximum number of minimal dominating sets that a graph on n vertices can have is known to be at most 1.7159 n. This upper bound might not be tight, since no examples of graphs with 1.5705 n or more minimal dominating sets are known. For several classes of graphs, we substantially improve the upper bound on the maximum number of minimal dominating sets in graphs on n vertices. In some cases, we provide examples of graphs whose number of minimal dominating sets exactly matches the proved upper bound for that class, thereby showing that these bounds are tight. For all considered graph classes, the upper bound proofs are constructive and can easily be transformed into algorithms enumerating all minimal dominating sets of the input graph. © 2012 Springer-Verlag.
Paris S.,Lita Inc
Proceedings Elmar - International Symposium Electronics in Marine | Year: 2010
Image quality assessment (QA) mimics the user's ability in evaluating image distortion. The presented technique uses a wavelet analysis and a distance measure associated to it. As often noticed, the wavelet analysis is a good approximation of the human visual system (HVS). The main contribution of this paper is the definition of a wavelet-based euclidean distance which embeds both, the deep-structure of the images and the specific orientation of every subband. This new definition of distance allows for an effective QA almost parameterless.
Bodlaender H.L.,University Utrecht |
Kratsch D.,Lita Inc
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011
In the game of Kayles, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyse the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = (V,E), if G[W] is connected and there exists an independent set X such that W = V - N[X], where N[X] is the union of X and the set of all vertices adjacent to at least one vertex of X. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We show that the number of K-sets in a graph with n vertices is bounded by O(1.6052 n ), and thus we have an algorithm for Kayles with running time O(1.6052 n ). We also show that the number of K-sets in a tree is bounded by n •3 n/3 and thus Kayles can be solved on trees in O(1.4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. © 2011 Springer-Verlag.
Boudjeloud-Assala L.,Lita Inc
International Journal of Bio-Inspired Computation | Year: 2012
Usual visualisation techniques for multidimensional datasets, such as parallel coordinates and scatterplot matrices, do not scale well to high numbers of dimensions. A common approach to solve this problem is dimensionality selection. Existing dimensionality selection techniques usually select pertinent dimension subsets that are significant to the user without loose of information. We present concrete cooperation between automatic algorithms, interactive algorithms and visualisation tools: the evolutionary algorithm is used to obtain optimal dimension subsets which represent the original dataset without loosing information for unsupervised mode (clustering or outlier detection). The last effective cooperation is a visualisation tool used to present the user interactive evolutionary algorithm results and let him actively participate in evolutionary algorithm searching with more efficiency resulting in a faster evolutionary algorithm convergence. We have implemented our approach and applied it to real dataset to confirm this approach is effective for supporting the user in the exploration of high dimensional datasets. Copyright © 2012 Inderscience Enterprises Ltd.
Stratulat S.,Lita Inc
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010
We give evidence of the direct integration and automated checking of implicit induction-based proofs inside certified reasoning environments, as that provided by the Coq proof assistant. This is the first step of a long term project focused on 1) mechanically certifying implicit induction proofs generated by automated provers like Spike, and 2) narrowing the gap between automated and interactive proof techniques inside proof assistants such that multiple induction steps can be executed completely automatically and mutual induction can be treated more conveniently. Contrary to the current approaches of reconstructing implicit induction proofs into scripts based on explicit induction tactics that integrate the usual proof assistants, our checking methodology is simpler and fits better for automation. The underlying implicit induction principles are separated and validated independently from the proof scripts that consist in a bunch of one-to-one translations of implicit induction proof steps. The translated steps can be checked independently, too, so the validation process fits well for parallelisation and for the management of large proof scripts. Moreover, our approach is more general; any kind of implicit induction proof can be considered because the limitations imposed by the proof reconstruction techniques no longer exist. An implementation that integrates automatic translators for generating fully checkable Coq scripts from Spike proofs is reported. © 2010 Springer-Verlag Berlin Heidelberg.
Gely A.,Lita Inc
CEUR Workshop Proceedings | Year: 2011
This paper is a preliminary attempt to study how modular and bimodular decomposition, used in graph theory, can be used on contexts and concept lattices in formal concept analysis (FCA). In a graph, a module is a set of vertices defined in term of behaviour with respect to the outside of the module: All vertices in the module act with no distinction and can be replaced by a unique vertex, which is a representation of the module. This definition may be applied to concepts of lattices, with slighty modifications (using order relation instead of adjacency). One can note that modular decomposition is not well suited for bipartite graphs. For example, every bipartite graph corresponding to a clarified context is trivially prime (not decomposable w.r.t modules). In , authors have introduced a decomposition dedicaced to bipartite graph, called the bimodular decomposition. In this paper, we show how modular decomposition of lattices and bimodular decomposition of contexts interact. These results may be used to improve readability of a Hasse diagram.
Rebai M.,University of Technology of Troyes |
Kacem I.,Lita Inc |
Adjallah K.H.,Metz National School of Engineering
Journal of Intelligent Manufacturing | Year: 2012
In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems. © 2010 Springer Science+Business Media, LLC.
Fouchal H.,University of Reims Champagne Ardenne |
Habbas Z.,Lita Inc
Concurrency Computation Practice and Experience | Year: 2013
In this paper, we propose a methodological approach to solve distributed nonbinary constraint satisfaction problem (CSP) on wireless sensor networks (WSNs). A distributed CSP is a CSP in which variables and constraints are distributed among multiple agents. On WSNs, it is usual to handle applications that need to solve distributed problems. Different real-world applications can be modeled as distributed CSPs, and numerous algorithms based on enumerative search have been proposed to solve them. The most cited one is distributed backtracking algorithm in which each variable is associated to each agent. This algorithm is known as fine-grained distributed algorithm. All the search efforts of this algorithm concerns the communication between agents that are very expensive. In addition, this approach is not realistic because, in general, an agent might control more than one variable. In this paper, we propose a generic methodology for developing coarse-grained backtracking algorithm. Mainly, a preprocess technique breaks a single large problem into a set of smaller connected ones. These semi-independent CSPs can be efficiently and concurrently solved and can cooperate to solve the whole problem. We illustrate the preprocess technique by the tree decomposition method for its good theoretical properties. The aim of our paper is to present an efficient approach to solve complex distributed CSPs over WSNs. Copyright © 2011 John Wiley & Sons, Ltd. Copyright © 2011 John Wiley & Sons, Ltd.