Masaki Yamamoto

Publication Activity (10 Years)

Years Active: 2005-2021
Publications (10 Years): 2

Top Topics

Undirected Graph

Linear Programming Relaxation

Optimization Problems

Top Venues

Theory Comput. Syst.

Discret. Appl. Math.

Australas. J Comb.

Publications

Naoki Matsumoto, Masaki Yamamoto, Masahito Yamazaki
The minimum number of vertices of graphs containing two monochromatic triangles for any edge $2$-coloring. Australas. J Comb. 81 (2021)
Masaki Yamamoto
Approximately counting paths and cycles in a graph. Discret. Appl. Math. 217 (2017)
Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets. CoRR (2014)
Masaki Yamamoto
A Combinatorial Analysis for the Critical Clause Tree. Theory Comput. Syst. 52 (2) (2013)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Derandomizing the HSSW Algorithm for 3-SAT. Algorithmica 67 (2) (2013)
Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems. SIAM J. Comput. 41 (4) (2012)
Masaki Yamamoto, Shuji Kijima, Yasuko Matsui
A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. J. Comb. Optim. 22 (3) (2011)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Derandomizing HSSW Algorithm for 3-SAT. COCOON (2011)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Derandomizing HSSW Algorithm for 3-SAT CoRR (2011)
Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto
Spectral Analysis of Random Sparse Matrices. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (6) (2011)
Masaki Yamamoto
A tighter lower bound on the circuit size of the hardest Boolean functions. Electron. Colloquium Comput. Complex. 18 (2011)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
An exact algorithm for the Boolean connectivity problem for k-CNF. Theor. Comput. Sci. 412 (35) (2011)
Tatsuya Akutsu, Avraham A. Melkman, Takeyuki Tamura, Masaki Yamamoto
Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions. J. Comput. Biol. 18 (10) (2011)
Masaki Yamamoto
A combinatorial analysis for the critical clause tree. Electron. Colloquium Comput. Complex. 17 (2010)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
-CNF. SAT (2010)
Osamu Watanabe, Masaki Yamamoto
Average-case analysis for the MAX-2SAT problem. Theor. Comput. Sci. 411 (16-18) (2010)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
On the Boolean connectivity problem for Horn relations. Discret. Appl. Math. 158 (18) (2010)
Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
An improved constant-time approximation algorithm for maximum matchings. STOC (2009)
Masaki Yamamoto, Shuji Kijima, Yasuko Matsui
A Polynomial-Time Perfect Sampler for the Q-Ising with a Vertex-Independent Noise. COCOON (2009)
Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto
An improved exact algorithm for the domatic number problem. Inf. Process. Lett. 101 (3) (2007)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
On the Boolean Connectivity Problem for Horn Relations. SAT (2007)
Masaki Yamamoto
A Spectral Method for MAX2SAT in the Planted Solution Model. ISAAC (2007)
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem. Electron. Colloquium Comput. Complex. 14 (029) (2007)
Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto
An Improved Exact Algorithm for the Domatic Number Problem CoRR (2006)
Masaki Yamamoto
Generating Instances for MAX2SAT with Optimal Solutions. Theory Comput. Syst. 39 (5) (2006)
Osamu Watanabe, Masaki Yamamoto
Average-Case Analysis for the MAX-2SAT Problem. SAT (2006)
Masaki Yamamoto
)-Time Deterministic Algorithm for SAT. ISAAC (2005)