Contraction and treewidth lower bounds.
Bodlaender, Hans L., Wolle, Thomas, Koster, Arie M.C.A. (2006)
Journal of Graph Algorithms and Applications
Similarity:
Bodlaender, Hans L., Wolle, Thomas, Koster, Arie M.C.A. (2006)
Journal of Graph Algorithms and Applications
Similarity:
Zsolt Tuza (1992)
Acta Universitatis Carolinae. Mathematica et Physica
Similarity:
Walshaw, Chris (2003)
Journal of Graph Algorithms and Applications
Similarity:
Morgan, Kerri, Farr, Graham (2007)
Journal of Graph Algorithms and Applications
Similarity:
Suderman, Matthew, Whitesides, Sue (2005)
Journal of Graph Algorithms and Applications
Similarity:
Shapira, Andrew (1997)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Niessen, Thomas (2001)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Jiří Matoušek, Jaroslav Nešetřil, Robin D. Thomas (1988)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
Harel, David, Koren, Yehuda (2002)
Journal of Graph Algorithms and Applications
Similarity:
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...