Coloring of graphs by partitioning
Ján Plesník (1980)
Mathematica Slovaca
Similarity:
Ján Plesník (1980)
Mathematica Slovaca
Similarity:
Walshaw, Chris (2003)
Journal of Graph Algorithms and Applications
Similarity:
Shapira, Andrew (1997)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Zsolt Tuza (1992)
Acta Universitatis Carolinae. Mathematica et Physica
Similarity:
François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very...
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...