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.
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...