Theory of Computing Systems 39(5) 723-742 2006年9月 [査読有り]
A test instance generator (an instance generator for short) for MAX2SAT is a procedure that produces, given a number n of variables, a 2-CNF formula F of n variables (randomly chosen from some reasonably large domain), and simultaneously provides ...
Proceedings - 2006 International Conference on Information and Communication Technologies: From Theory to Applications, ICTTA 2006 2 2792-2797 2006年 [査読有り]
The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695™ (up to polynomial factors). This result improves the previo...
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2006, PROCEEDINGS 4121 277-282 2006年 [査読有り]
We propose a "planted solution model" for discussing the average-case complexity of the MAX-2SAT problem. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pair) is the optimal solution...
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 644-653 2005年 [査読有り]
We improve an upper bound by Hirsch on a deterministic algorithm for solving general CNF satisfiability problem. With more detail analysis of Hirsch's algorithm, we give some improvements, by which we can prove an upper bound Õ(1.234 m) w.r.t. the...
経済学部 教員紹介
理工学部 教員紹介
法科大学院 教員紹介（リンク）