Titlebook: Computing and Combinatorics; 17th Annual Internat Bin Fu,Ding-Zhu Du Conference proceedings 2011 Springer-Verlag GmbH Berlin Heidelberg 201

cravat

鸽子

巧办法

,A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability,Recently, Moser and Tardos [MT10] came up with a . proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

musicologist

Computing and Combinatorics978-3-642-22685-4Series ISSN 0302-9743 Series E-ISSN 1611-3349

MEET

Hans Dieter Baehr,Stephan Kabelacnal complexity of this problem was open in the past. In this paper, we show that this problem is NP-hard, and present a parameterized algorithm based on a refined search tree technique with a running time of .(4.612. + |.|.)), which improves the trivial algorithm of running time .(6. + |.|.).

helper-T-cells

ASTER

现晕光

Bin Fu,Ding-Zhu DuUp-to-date results.Fast-track conference proceedings.State-of-the-art research

贪婪性

Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/234771.jpg

Pde5-Inhibitors

Diffusion and Thermodiffusion in Alloys,ynomial-time algorithms to count the number of dominating sets (and minimum dominating sets) in interval graphs and trapezoid graphs. They are based on dynamic programming. With the help of dynamic update on a binary tree, we further reduce the time complexity. On the other hand, we prove that count