Mihalis Yannakakis

Top papers

• Optimization, approximation, and complexity classes

  Christos H. Papadimitriou, Mihalis Yannakakis·1991·Journal of Computer and System Sciences
  ↗ 1,656
• Principles and methods of testing finite state machines-a survey

  D. Lee, Mihalis Yannakakis·1996·Proceedings of the IEEE
  ↗ 1,214
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

  Robert E. Tarjan, Mihalis Yannakakis·1984·SIAM Journal on Computing
  ↗ 1,042
• On the hardness of approximating minimization problems

  Carsten Lund, Mihalis Yannakakis·1994·Journal of the ACM
  ↗ 888OA
• On the Desirability of Acyclic Database Schemes

  Catriel Beeri, Ronald Fagin, David Maier, et al.·1983·Journal of the ACM
  ↗ 800OA
• On generating all maximal independent sets

  David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou·1988·Information Processing Letters
  ↗ 765
• How easy is local search?

  David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis·1988·Journal of Computer and System Sciences
  ↗ 711OA
• Computing the Minimum Fill-In is NP-Complete

  Mihalis Yannakakis·1981·SIAM Journal on Algebraic and Discrete Methods
  ↗ 707
• The Complexity of Multiterminal Cuts

  Elias Dahlhaus, D. S. Johnson, Christos H. Papadimitriou, et al.·1994·SIAM Journal on Computing
  ↗ 661
• The complexity of probabilistic verification

  Costas Courcoubetis, Mihalis Yannakakis·1995·Journal of the ACM
  ↗ 557OA
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations

  Kousha Etessami, Mihalis Yannakakis·2009·Journal of the ACM
  ↗ 518
• Expressing combinatorial optimization problems by Linear Programs

  Mihalis Yannakakis·1991·Journal of Computer and System Sciences
  ↗ 518