Zobrazeno 1 - 10
of 28
pro vyhledávání: '"Moser, Robin A."'
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the connectivity-related notion of tightness for hypergraphs introduced by A
Externí odkaz:
http://arxiv.org/abs/1109.3390
A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical variables of a CNF formula, we improve the running time for 3-SAT from O
Externí odkaz:
http://arxiv.org/abs/1009.4830
Autor:
Moser, Robin A., Scheder, Dominik
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O((a+epsilon)^n * poly(n)), where epsilon > 0 can be made arbit
Externí odkaz:
http://arxiv.org/abs/1008.4067
For an integer d>=1, let tau(d) be the smallest integer with the following property: If v1,v2,...,vt is a sequence of t>=2 vectors in [-1,1]^d with v1+v2+...+vt in [-1,1]^d, then there is a subset S of {1,2,...,t} of indices, 2<=|S|<=tau(d), such tha
Externí odkaz:
http://arxiv.org/abs/0912.0424
Autor:
Moser, Robin A., Tardos, Gábor
The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be g
Externí odkaz:
http://arxiv.org/abs/0903.0544
Autor:
Moser, Robin A.
The Lovasz Local Lemma [EL75] is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which
Externí odkaz:
http://arxiv.org/abs/0810.4812
Autor:
Moser, Robin A.
The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. Kratochvil et al. applied this technique to prove that a k-CNF in which each varia
Externí odkaz:
http://arxiv.org/abs/0807.2120
Autor:
MOSER, ROBIN A.1 robin.moser@inf.ethz.ch, TARDOS, GÁBOR2 tardos@cs.sfu.ca
Publikováno v:
Journal of the ACM. Jan2010, Vol. 57 Issue 2, p11-11:15. 15p. 1 Diagram.
