EuDML | Browse

Page 1

Displaying 1 – 7 of 7

Satisfiability and matchings in bipartite graphs: relationship and tractability.

Belaid Benhamou (2004)

RACSAM

Satisfiability problem is the task to establish either a given CNF logical formula admits a model or not. It is known to be the canonical NP-complete problem. We study in this note the relationship between matchings in bipartite graphs and the satisfiability problem, and prove that some restrictions of formulae including the known r-r-SAT1 class are trivially satisfiable. We present an algorithm which finds a model for such formulas in polynomial time complexity if one exists or, failing this, proves...

Secuenciación dinámica de sistemas de fabricación flexible mediante aprendizaje automático: análisis de los principales sistemas de secuenciación existentes.

Paolo Priore, David de la Fuente, Javier Puente, Alberto Gómez (2001)

Qüestiió

Una forma habitual de secuenciar de modo dinámico los trabajos en los sistemas de fabricación es mediante el empleo de reglas de secuenciación. Sin embargo, el problema que presenta este método es que el comportamiento del sistema de fabricación dependerá de su estado, y no existe una regla que supere a las demás en todos los posibles estados que puede presentar el sistema de fabricación. Por lo tanto, sería interesante usar en cada momento la regla más adecuada. Para lograr este objetivo, se pueden...

Selection of search strategies for solving 3-sat problems

Andrzej Pułka (2014)

International Journal of Applied Mathematics and Computer Science

Simplifying the propositional satisfiability problem by sub-model propagation.

Kusper, Gábor, Csõke, Lajos, Kovásznai, Gergely (2008)

Annales Mathematicae et Informaticae

Smooth and sharp thresholds for random $k$ -XOR-CNF satisfiability

Nadia Creignou, Hervé Daudé (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The aim of this paper is to study the threshold behavior for the satisfiability property of a random $k$ -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with $k$ variables per equation. For $k \geq 3$ we show the existence of a sharp threshold for the satisfiability of a random $k$ -XOR-CNF formula, whereas there are smooth thresholds for $k = 1$ and $k = 2$ .

Solving maximum independent set by asynchronous distributed hopfield-type neural networks

Giuliano Grossi, Massimo Marchi, Roberto Posenato (2006)

RAIRO - Theoretical Informatics and Applications

We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the...

Solving single and multiobjective models for an assembly line design problem through ant colony algorithms.

Hicham Chehade, Farouk Yalaoui, Lionel Amodeo (2009)

Mathware and Soft Computing