Masaki Yamamoto

According to our database, Masaki Yamamoto authored at least 20 papers between 2005 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

The minimum number of vertices of graphs containing two monochromatic triangles for any edge $2$-coloring.

Naoki Matsumoto, Masaki Yamamoto, Masahito Yamazaki

Australas. J Comb., 2021

2017

Approximately counting paths and cycles in a graph.

Masaki Yamamoto

Discret. Appl. Math., 2017

2014

Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets.

Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto

CoRR, 2014

2013

Derandomizing the HSSW Algorithm for 3-SAT.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Algorithmica, 2013

2012

Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems.

Yuichi Yoshida, Masaki Yamamoto, Hiro Ito

SIAM J. Comput., 2012

2011

An exact algorithm for the Boolean connectivity problem for k-CNF.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Theor. Comput. Sci., 2011

A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise.

Masaki Yamamoto, Shuji Kijima, Yasuko Matsui

J. Comb. Optim., 2011

Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions.

Tatsuya Akutsu, Avraham A. Melkman, Takeyuki Tamura, Masaki Yamamoto

J. Comput. Biol., 2011

Spectral Analysis of Random Sparse Matrices.

Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2011

A tighter lower bound on the circuit size of the hardest Boolean functions.

Masaki Yamamoto

Electron. Colloquium Comput. Complex., 2011

2010

Average-case analysis for the MAX-2SAT problem.

Osamu Watanabe, Masaki Yamamoto

Theor. Comput. Sci., 2010

A combinatorial analysis for the critical clause tree.

Masaki Yamamoto

Electron. Colloquium Comput. Complex., 2010

On the Boolean connectivity problem for Horn relations.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Discret. Appl. Math., 2010

An Exact Algorithm for the Boolean Connectivity Problem for <i>k</i>-CNF.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

2009

An improved constant-time approximation algorithm for maximum matchings.

Yuichi Yoshida, Masaki Yamamoto, Hiro Ito

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2007

An improved exact algorithm for the domatic number problem.

Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto

Inf. Process. Lett., 2007

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Electron. Colloquium Comput. Complex., 2007

A Spectral Method for MAX2SAT in the Planted Solution Model.

Masaki Yamamoto

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

Generating Instances for MAX2SAT with Optimal Solutions.

Masaki Yamamoto

Theory Comput. Syst., 2006

2005

An Improved O(1.234^m)-Time Deterministic Algorithm for SAT.

Masaki Yamamoto

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005