On the average case complexity of some P-complete problems
Maria Serna, Fatos Xhafa (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying similar documents to “Experimental comparison of 2-satisfiability algorithms”
On the average case complexity of some P-complete problems
An almost naive algorithm for finding relative neighbourhood graphs in metrics
Jyrki Katajainen, Olli Nevalainen (1987)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
On the distributed decision-making complexity of the minimum vertex cover problem
Pierluigi Crescenzi, Luca Trevisan (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
A. Aiello, E. Burattini, A. Massarotti (1977)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
Jean-Luc Lutton, Ernesto Bonomi (1986)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Accelerating backtrack search with a best-first-search strategy
Zoltán Ádám Mann, Tamás Szép (2014)
International Journal of Applied Mathematics and Computer Science
Similarity:
Accelerating backtrack search with a best-first-search strategy
Zoltán Ádám Mann, Tamás Szép (2014)
International Journal of Applied Mathematics and Computer Science
Similarity:
Spanning trees with low crossing number
Jiří Matoušek (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Satisfiability and matchings in bipartite graphs: relationship and tractability.
Belaid Benhamou (2004)
RACSAM
Similarity:
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-SAT class are trivially satisfiable. We present an algorithm which finds a model for such formulas in polynomial time complexity if one exists or, failing...