scientific article; zbMATH DE number 6469161

MaRDI QIDQ5501274zbMATH OpenFDO

Authors Suguru Tamaki, Kazuo Iwama

Publication date 3 August 2015

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited in

(19)

• A combinatorial analysis for the critical clause tree
• New methods for 3-SAT decision and worst-case analysis
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• k-SAT Is No Harder Than Decision-Unique-k-SAT
• The Time Complexity of Constraint Satisfaction
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• An Improved Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes
• Towards NP-P via proof complexity and search
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• Walksat Stalls Well Below Satisfiability
• A randomized algorithm for 3-SAT
• An exact algorithm for the Boolean connectivity problem for k-CNF
• PPSZ for general k-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• An improved exact algorithm for the domatic number problem
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Modelling the dynamics of stochastic local search on \(k\)-SAT
• Computing branchwidth via efficient triangulations and blocks

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501274)