Edit Profile (opens in new tab) Yannakakis, Mihalis Compute Distance To: Compute Author ID: yannakakis.mihalis Published as: Yannakakis, Mihalis; Yannakakis, M.; Yannakakis, Milhalis Homepage: http://www1.cs.columbia.edu/%7emihalis/ External Links: MGP · ORCID · Wikidata · Google Scholar · ResearchGate · dblp Documents Indexed: 163 Publications since 1978 1 Contribution as Editor Co-Authors: 83 Co-Authors with 132 Joint Publications 2,652 Co-Co-Authors all top 5 Co-Authors 29 single-authored 29 Papadimitriou, Christos Harilaos 27 Etessami, Kousha 10 Vazirani, Vijay V. 9 Stewart, Alistair 7 Courcoubetis, Costas A. 7 Diakonikolas, Ilias 7 Vardi, Moshe Ya’akov 6 Alur, Rajeev 6 Chen, Xi 6 Garg, Naveen Kumar 6 Peled, Doron A. 5 Paparas, Dimitris 4 Johnson, David Stifler 4 Ullman, Jeffrey David 3 Coffman, Edward Grady jun. 3 Groce, Alex 3 Lund, Carsten 3 Maier, David 3 Soltan, Saleh 3 Tarjan, Robert Endre 3 Zussman, Gil 2 Cosmadakis, Stavros S. 2 Daskalakis, Constantinos 2 Fagin, Ronald 2 Gavril, Fanica 2 Guruswami, Venkatesan 2 Khanna, Sanjeev 2 Kupferman, Orna 2 Kurshan, Robert P. 2 Kwiatkowska, Marta Z. 2 Rajaraman, Rajmohan 2 Sagiv, Yehoshua 2 Shepherd, Bruce 2 Sun, Xiaorui 2 Vassilvitskii, Sergei 2 Wojtczak, Dominik 2 Wolper, Pierre 1 Afrati, Foto N. 1 Aho, Alfred Vaino 1 Arkin, Esther M. 1 Beeri, Catriel 1 Blum, Avrim L. 1 Blum, Manuel 1 Chaudhuri, Swarat 1 Crescenzi, Pierluigi 1 Dahlhaus, Elias 1 Garey, Michael Randolph 1 Godefroid, Patrice 1 Goldman, Deborah 1 Graham, Marc H. 1 Guha, Sudipto 1 Guo, Chenghao 1 Hadzilacos, Thanasis 1 Holzmann, Gerard J. 1 Honeyman, Peter 1 Itai, Alon 1 Jiang, Tao 1 Kanellakis, Paris Christos 1 Kannan, Sampath K. 1 Karp, Richard Manning 1 Koutsoupias, Elias 1 Ladner, Richard E. 1 Lewis, John M. 1 Li, Ming 1 Liu, Christine 1 Lustig, Yoad 1 Magazine, Michael J. 1 Matikas, George 1 Mosk-Aoyama, Damon 1 Nozari, Ardavan 1 Pavlidis, Theodosios 1 Piccolboni, Antonio 1 Santos, Cipriano 1 Schäffer, Alejandro A. 1 Serafini, Paolo 1 Seymour, Paul D. 1 Tromp, John T. 1 Vempala, Santosh S. 1 Vlatakis-Gkaragkounis, Emmanouil V. 1 Vornberger, Oliver 1 Wolfson, Ouri 1 Wyner, Aaron D. 1 Zhang, Xinzhi all top 5 Serials 17 Journal of Computer and System Sciences 17 SIAM Journal on Computing 12 Journal of the Association for Computing Machinery 5 Information Processing Letters 5 Journal of the ACM 4 Mathematics of Operations Research 4 Theoretical Computer Science 3 SIAM Journal on Algebraic and Discrete Methods 2 Discrete Applied Mathematics 2 IEEE Transactions on Computers 2 Information and Control 2 Journal of Algorithms 2 Information and Computation 2 Logical Methods in Computer Science 1 Computers & Mathematics with Applications 1 IEEE Transactions on Automatic Control 1 Journal of Combinatorial Theory. Series B 1 Kiberneticheskiĭ Sbornik. Novaya Seriya 1 Operations Research 1 Combinatorica 1 Algorithmica 1 Annals of Operations Research 1 Games and Economic Behavior 1 Pokroky Matematiky, Fyziky & Astronomie 1 Proceedings of the National Academy of Sciences of the United States of America 1 SIAM Journal on Applied Mathematics 1 Formal Methods in System Design 1 Annals of Mathematics and Artificial Intelligence 1 Journal of Automata, Languages and Combinatorics 1 Logic Journal of the IGPL 1 ACM Transactions on Computational Logic 1 ACM Transactions on Algorithms 1 Computer Science Review 1 ACM Transactions on Computation Theory 1 IEEE Transactions on Control of Network Systems all top 5 Fields 146 Computer science (68-XX) 43 Operations research, mathematical programming (90-XX) 33 Combinatorics (05-XX) 24 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Probability theory and stochastic processes (60-XX) 6 Information and communication theory, circuits (94-XX) 5 Mathematical logic and foundations (03-XX) 5 Numerical analysis (65-XX) 3 Systems theory; control (93-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Number theory (11-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Convex and discrete geometry (52-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 143 Publications have been cited 4,827 times in 3,888 Documents Cited by ▼ Year ▼ Optimization, approximation, and complexity classes. Zbl 0765.68036Papadimitriou, Christos H.; Yannakakis, Mihalis 400 1991 Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. Zbl 0545.68062Tarjan, Robert E.; Yannakakis, Mihalis 253 1984 The complexity of multiterminal cuts. Zbl 0809.68075Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 183 1994 On generating all maximal independent sets. Zbl 0654.68086Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 172 1988 The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029Lewis, John M.; Yannakakis, Mihalis 168 1980 On the desirability of acyclic database schemes. Zbl 0624.68087Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis 167 1983 Computing the minimum fill-in is NP-complete. Zbl 0496.68033Yannakakis, Mihalis 166 1981 The complexity of the partial order dimension problem. Zbl 0516.06001Yannakakis, Mihalis 160 1982 On the hardness of approximating minimization problems. Zbl 0814.68064Lund, Carsten; Yannakakis, Mihalis 156 1994 Node-and edge-deletion NP-complete problems. Zbl 1282.68131Yannakakis, Mihalis 152 1978 Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074Yannakakis, Mihalis 151 1991 Edge dominating sets in graphs. Zbl 0455.05047Yannakakis, M.; Gavril, F. 134 1980 How easy is local search? Zbl 0655.68074Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 133 1988 Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075Garg, N.; Vazirani, V. V.; Yannakakis, M. 104 1997 Node-deletion problems on bipartite graphs. Zbl 0468.05044Yannakakis, M. 102 1981 The complexity of facets (and some facets of complexity). Zbl 0571.68028Papadimitriou, C. H.; Yannakakis, M. 99 1984 The complexity of probabilistic verification. Zbl 0885.68109Courcoubetis, Costas; Yannakakis, Mihalis 88 1995 The traveling salesman problem with distances one and two. Zbl 0778.90057Papadimitriou, Christos H.; Yannakakis, Mihalis 88 1993 Shortest paths without a map. Zbl 0733.68065Papadimitriou, Christos H.; Yannakakis, Mihalis 80 1991 Edge-deletion problems. Zbl 0468.05043Yannakakis, Mihalis 70 1981 Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 66 1996 Embedding planar graphs in four pages. Zbl 0673.05022Yannakakis, Mihalis 63 1989 Multiway cuts in node weighted graphs. Zbl 1068.68178Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 59 2004 Scheduling interval-ordered tasks. Zbl 0421.68040Papadimitriou, C. H.; Yannakakis, M. 59 1979 Batch sizing and job sequencing on a single machine. Zbl 0712.90035Coffman, E. G. jun.; Yannakakis, M.; Magazine, M. J.; Santos, C. 54 1990 On the hardness of approximating minimization problems. Zbl 1310.68094Lund, Carsten; Yannakakis, Mihalis 52 1993 The maximum k-colorable subgraph problem for chordal graphs. Zbl 0653.68070Yannakakis, Mihalis; Gavril, Fanica 51 1987 Simple local search problems that are hard to solve. Zbl 0716.68048Schäffer, Alejandro A.; Yannakakis, Mihalis 48 1991 On the complexity of Nash equilibria and other fixed points. Zbl 1204.91003Etessami, Kousha; Yannakakis, Mihalis 47 2010 The complexity of restricted spanning tree problems. Zbl 0478.68068Papadimitriou, Christos H.; Yannakakis, Mihalis 46 1982 Markov decision processes and regular events. Zbl 0954.90061Courcoubetis, Costas; Yannakakis, Mihalis 45 1998 Equivalences among relational expressions with the union and difference operators. Zbl 0456.68123Sagiv, Yehoshua; Yannakakis, Mihalis 39 1980 A polynomial algorithm for the min-cut linear arrangement of trees. Zbl 0633.68063Yannakakis, Mihalis 38 1985 On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031Papadimitriou, Christos H.; Yannakakis, Mihalis 37 1996 Optimal scheduling of products with two subassemblies on a single machine. Zbl 0672.90075Coffman, Edward G. jun.; Nozari, Ardavan; Yannakakis, Mihalis 36 1989 Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032Papadimitriou, Christos H.; Yannakakis, Mihalis 34 1990 On the approximation of maximum satisfiability. Zbl 0820.68056Yannakakis, Mihalis 31 1994 Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1325.68091Etessami, Kousha; Yannakakis, Mihalis 31 2009 Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076Vazirani, Vijay V.; Yannakakis, Milhalis 30 1989 Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis 29 2003 Linear approximation of shortest superstrings. Zbl 0812.68075Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis 29 1994 On the complexity of database queries. Zbl 0939.68024Papadimitriou, Christos H.; Yannakakis, Mihalis 24 1999 On a class of totally unimodular matrices. Zbl 0565.90042Yannakakis, Mihalis 24 1985 The approximation of maximum subgraph problems. Zbl 1422.68087Lund, Carsten; Yannakakis, Mihalis 24 1993 Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 23 1993 A note on succinct representations of graphs. Zbl 0616.68041Papadimitriou, Christos H.; Yannakakis, Mihalis 21 1986 Scheduling opposing forests. Zbl 0507.68021Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M. 21 1983 Searching a fixed graph. Zbl 1045.90532Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis 20 1996 The effect of a connectivity requirement on the complexity of maximum subgraph problems. Zbl 0421.68047Yannakakis, Mihalis 20 1979 Addendum to “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs”. Zbl 0562.68055Tarjan, Robert E.; Yannakakis, Mihalis 20 1985 Minimum and maximum delay problems in real-time systems. Zbl 0777.68045Courcoubetis, Costas; Yannakakis, Mihalis 20 1992 On the complexity of protein folding (extended abstract). Zbl 1007.68511Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis 18 1998 Memory efficient algorithms for the verification of temporal properties. Zbl 0786.68060Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M. 18 1991 On complexity as bounded rationality (extended abstract). Zbl 1345.68216Papadimitriou, Christos H.; Yannakakis, Mihalis 18 1994 Multi-objective model checking of Markov decision processes. Zbl 1161.68565Etessami, Kousha; Kwiatkowska, Marta; Vardi, Moshe Y.; Yannakakis, Mihalis 17 2008 High-probability parallel transitive-closure algorithms. Zbl 0716.68041Ullman, Jeffrey D.; Yannakakis, Mihalis 17 1991 Small approximate Pareto sets for biobjective shortest paths and other problems. Zbl 1198.90346Diakonikolas, Ilias; Yannakakis, Mihalis 17 2009 Testing finite-state machines: state identification and verification. Zbl 1395.68173Lee, David; Yannakakis, Mihalis 16 1994 Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1118.68497Etessami, Kousha; Yannakakis, Mihalis 16 2005 Recursive Markov decision processes and recursive stochastic games. Zbl 1085.68089Etessami, Kousha; Yannakakis, Mihalis 16 2005 Distinguishing tests for nondeterministic and probabilistic machines. Zbl 0978.68522Alur, Rajeev; Courcoubetis, Costas; Yannakakis, Mihalis 15 1995 On nested depth first search. Zbl 0880.68084Holzmann, Gerard J.; Peled, Doron; Yannakakis, Mihalis 15 1997 Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042Vazirani, Vijay V.; Yannakakis, Mihalis 14 2011 Efficiently computing succinct trade-off curves. Zbl 1080.90069Vassilvitskii, Sergei; Yannakakis, Mihalis 14 2005 Linear programming without the matrix. Zbl 1310.90073Papadimitriou, Christos H.; Yannakakis, Mihalis 14 1993 On the complexity of testing implications of functional and join dependencies. Zbl 0481.68094Maier, David; Sagiv, Yehoshua; Yannakakis, Mihalis 13 1981 The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M. 13 1981 Algebraic dependencies. Zbl 0493.68095Yannakakis, Mihalis; Papadimitriou, Christos H. 13 1982 Modularity of cycles and paths in graphs. Zbl 0799.68146Arkin, E. M.; Papadimitriou, C. H.; Yannakakis, M. 13 1991 Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis 13 1999 Black box checking. Zbl 0952.68012Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis 12 1999 Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 12 1994 Recursive concurrent stochastic games. Zbl 1133.91317Etessami, Kousha; Yannakakis, Mihalis 12 2006 The analysis of local search problems and their heuristics. Zbl 0778.90058Yannakakis, Mihalis 11 1990 Computational complexity. Zbl 0966.90506Yannakakis, Mihalis 10 1997 Black box checking. Zbl 1046.68072Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis 10 2002 Timing verification by successive approximation. Zbl 0939.68705Alur, R.; Itai, A.; Kurshan, R. P.; Yannakakis, M. 10 1995 Testing the universal instance assumption. Zbl 0422.68048Honeyman, Peter; Ladner, Richard E.; Yannakakis, Mihalis 10 1980 Permuting elements within columns of a matrix in order to minimize maximum row sum. Zbl 0551.90042Coffman, E. G. jun.; Yannakakis, M. 10 1984 Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. Zbl 1286.68188Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 10 2012 Algorithmic verification of recursive probabilistic state machines. Zbl 1087.68054Etessami, Kousha; Yannakakis, Mihalis 9 2005 Adaptive model checking. Zbl 1043.68570Groce, Alex; Peled, Doron; Yannakakis, Mihalis 9 2002 Cutting and partitioning a graph after a fixed pattern. Zbl 0549.68062Yannakakis, Mihalis; Kanellakis, Paris C.; Cosmadakis, Stavros S.; Papadimitriou, Christos H. 9 1983 Independent database schemas. Zbl 0603.68099Graham, Marc H.; Yannakakis, Mihalis 9 1984 Memory efficient algorithms for the verification of temporal properties. Zbl 0765.68120Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M. 9 1991 A theory of safe locking policies in database systems. Zbl 0488.68071Yannakakis, Mihalis 9 1982 Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. Zbl 1272.68458Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 8 2012 Analysis of recursive state machines. Zbl 0991.68535Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 8 2001 Realizability and verification of MSC graphs. Zbl 1088.68097Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 8 2005 On recognizing integer polyhedra. Zbl 0718.68044Papadimitriou, C. H.; Yannakakis, M. 8 1990 Markov decision processes and regular events. Zbl 0765.68152Courcoubetis, Costas; Yannakakis, Mihalis 8 1990 Serializability by locking. Zbl 0631.68078Yannakakis, Mihalis 8 1984 On the value of information in distributed decision-making (extended abstract). Zbl 1314.91068Papadimitriou, Christos H.; Yannakakis, Mihalis 8 1991 Model checking of recursive probabilistic systems. Zbl 1351.68159Etessami, Kousha; Yannakakis, Mihalis 8 2012 The complexity of non-monotone markets. Zbl 1293.91065Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 8 2013 Realizability and verification of MSC graphs. Zbl 0986.68518Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 7 2001 Recursive Markov decision processes and recursive stochastic games. Zbl 1333.91005Etessami, Kousha; Yannakakis, Mihalis 7 2015 Tie-breaking semantics and structural totality. Zbl 0864.68028Papadimitriou, Christos H.; Yannakakis, Mihalis 6 1997 Recursive stochastic games with positive rewards. Zbl 1153.91328Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis 6 2008 Succinct approximate convex Pareto curves. Zbl 1192.90190Diakonikolas, Ilias; Yannakakis, Mihalis 6 2008 Planar graphs that need four pages. Zbl 1448.05055Yannakakis, Mihalis 2 2020 The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis 3 2018 Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Zbl 1394.60085Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 1 2018 On the complexity of simple and optimal deterministic mechanisms for an additive buyer. Zbl 1403.91163Chen, Xi; Matikas, George; Paparas, Dimitris; Yannakakis, Mihalis 1 2018 The complexity of non-monotone markets. Zbl 1427.91130Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 3 2017 Doubly balanced connected graph partitioning. Zbl 1410.05172Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil 1 2017 A polynomial time algorithm for computing extinction probabilities of multitype branching processes. Zbl 1378.68074Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 1 2017 How good is the Chord algorithm? Zbl 1344.68284Daskalakis, Constantinos; Diakonikolas, Ilias; Yannakakis, Mihalis 1 2016 Recursive Markov decision processes and recursive stochastic games. Zbl 1333.91005Etessami, Kousha; Yannakakis, Mihalis 7 2015 Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Zbl 1394.60084Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 5 2015 Upper bounds for Newton’s method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata. Zbl 1426.68177Stewart, Alistair; Etessami, Kousha; Yannakakis, Mihalis 4 2015 A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. Zbl 1321.68309Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 1 2014 The complexity of non-monotone markets. Zbl 1293.91065Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 8 2013 Stochastic context-free grammars, regular languages, and newton’s method. Zbl 1334.68111Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 2 2013 Analysis of Boolean programs. Zbl 1381.68164Godefroid, Patrice; Yannakakis, Mihalis 1 2013 Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. Zbl 1286.68188Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 10 2012 Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. Zbl 1272.68458Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis 8 2012 Model checking of recursive probabilistic systems. Zbl 1351.68159Etessami, Kousha; Yannakakis, Mihalis 8 2012 Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042Vazirani, Vijay V.; Yannakakis, Mihalis 14 2011 Temporal synthesis for bounded systems and environments. Zbl 1230.68144Kupferman, Orna; Lustig, Yoad; Vardi, Moshe Y.; Yannakakis, Mihalis 2 2011 On the complexity of Nash equilibria and other fixed points. Zbl 1204.91003Etessami, Kousha; Yannakakis, Mihalis 47 2010 An impossibility theorem for price-adjustment mechanisms. Zbl 1205.91067Papadimitriou, Christos H.; Yannakakis, Mihalis 3 2010 How good is the chord algorithm? Zbl 1288.68261Daskalakis, Constantinos; Diakonikolas, Ilias; Yannakakis, Mihalis 2 2010 Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1325.68091Etessami, Kousha; Yannakakis, Mihalis 31 2009 Small approximate Pareto sets for biobjective shortest paths and other problems. Zbl 1198.90346Diakonikolas, Ilias; Yannakakis, Mihalis 17 2009 Equilibria, fixed points, and complexity classes. Zbl 1302.68143Yannakakis, Mihalis 4 2009 Computational aspects of equilibria. Zbl 1253.91004Yannakakis, Mihalis 1 2009 Multi-objective model checking of Markov decision processes. Zbl 1161.68565Etessami, Kousha; Kwiatkowska, Marta; Vardi, Moshe Y.; Yannakakis, Mihalis 17 2008 Recursive stochastic games with positive rewards. Zbl 1153.91328Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis 6 2008 Succinct approximate convex Pareto curves. Zbl 1192.90190Diakonikolas, Ilias; Yannakakis, Mihalis 6 2008 Recursive concurrent stochastic games. Zbl 1161.68619Etessami, Kousha; Yannakakis, Mihalis 4 2008 Equilibria, fixed points, and complexity classes. Zbl 1259.68075Yannakakis, Mihalis 2 2008 Multi-objective model checking of Markov decision processes. Zbl 1186.68286Etessami, K.; Kwiatkowska, M.; Vardi, M. Y.; Yannakakis, M. 5 2007 Recursive concurrent stochastic games. Zbl 1133.91317Etessami, Kousha; Yannakakis, Mihalis 12 2006 Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games. Zbl 1136.90499Etessami, Kousha; Yannakakis, Mihalis 6 2006 Adaptive model checking. Zbl 1108.68073Groce, Alex; Peled, Doron; Yannakakis, Mihalis 1 2006 Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1118.68497Etessami, Kousha; Yannakakis, Mihalis 16 2005 Recursive Markov decision processes and recursive stochastic games. Zbl 1085.68089Etessami, Kousha; Yannakakis, Mihalis 16 2005 Efficiently computing succinct trade-off curves. Zbl 1080.90069Vassilvitskii, Sergei; Yannakakis, Mihalis 14 2005 Algorithmic verification of recursive probabilistic state machines. Zbl 1087.68054Etessami, Kousha; Yannakakis, Mihalis 9 2005 Realizability and verification of MSC graphs. Zbl 1088.68097Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 8 2005 Multiway cuts in node weighted graphs. Zbl 1068.68178Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 59 2004 Efficiently computing succinct trade-off curves. Zbl 1099.90577Vassilvitskii, Sergei; Yannakakis, Mihalis 5 2004 Testing, optimizaton, and games. Zbl 1099.68662Yannakakis, Mihalis 2 2004 Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis 29 2003 Compression of partially ordered strings. Zbl 1274.68118Alur, Rajeev; Chaudhuri, Swarat; Etessami, Kousha; Guha, Sudipto; Yannakakis, Mihalis 1 2003 Black box checking. Zbl 1046.68072Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis 10 2002 Adaptive model checking. Zbl 1043.68570Groce, Alex; Peled, Doron; Yannakakis, Mihalis 9 2002 Closed partition lattice and machine decomposition. Zbl 1392.68270Lee, David; Yannakakis, Mihalis 1 2002 Analysis of recursive state machines. Zbl 0991.68535Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 8 2001 Realizability and verification of MSC graphs. Zbl 0986.68518Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis 7 2001 Approximation of multiobjective optimization problems. Zbl 0997.68563Yannakakis, Mihalis 1 2001 On the complexity of database queries. Zbl 0939.68024Papadimitriou, Christos H.; Yannakakis, Mihalis 24 1999 Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis 13 1999 Black box checking. Zbl 0952.68012Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis 12 1999 A convex relaxation for the asymmetric TSP. Zbl 1008.90519Vempala, Santosh; Yannakakis, Mihalis 3 1999 Markov decision processes and regular events. Zbl 0954.90061Courcoubetis, Costas; Yannakakis, Mihalis 45 1998 On the complexity of protein folding (extended abstract). Zbl 1007.68511Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis 18 1998 Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075Garg, N.; Vazirani, V. V.; Yannakakis, M. 104 1997 On nested depth first search. Zbl 0880.68084Holzmann, Gerard J.; Peled, Doron; Yannakakis, Mihalis 15 1997 Computational complexity. Zbl 0966.90506Yannakakis, Mihalis 10 1997 Tie-breaking semantics and structural totality. Zbl 0864.68028Papadimitriou, Christos H.; Yannakakis, Mihalis 6 1997 Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 66 1996 On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031Papadimitriou, Christos H.; Yannakakis, Mihalis 37 1996 Searching a fixed graph. Zbl 1045.90532Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis 20 1996 The complexity of probabilistic verification. Zbl 0885.68109Courcoubetis, Costas; Yannakakis, Mihalis 88 1995 Distinguishing tests for nondeterministic and probabilistic machines. Zbl 0978.68522Alur, Rajeev; Courcoubetis, Costas; Yannakakis, Mihalis 15 1995 Timing verification by successive approximation. Zbl 0939.68705Alur, R.; Itai, A.; Kurshan, R. P.; Yannakakis, M. 10 1995 On datalog vs polynomial time. Zbl 0831.68015Afrati, Foto; Cosmandakis, Stavros S.; Yannakakis, Mihalis 5 1995 Testing finite state machines: Fault detection. Zbl 0826.68044Yannakakis, Mihalis; Lee, David 3 1995 The complexity of multiterminal cuts. Zbl 0809.68075Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 183 1994 On the hardness of approximating minimization problems. Zbl 0814.68064Lund, Carsten; Yannakakis, Mihalis 156 1994 On the approximation of maximum satisfiability. Zbl 0820.68056Yannakakis, Mihalis 31 1994 Linear approximation of shortest superstrings. Zbl 0812.68075Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis 29 1994 On complexity as bounded rationality (extended abstract). Zbl 1345.68216Papadimitriou, Christos H.; Yannakakis, Mihalis 18 1994 Testing finite-state machines: state identification and verification. Zbl 1395.68173Lee, David; Yannakakis, Mihalis 16 1994 Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 12 1994 The traveling salesman problem with distances one and two. Zbl 0778.90057Papadimitriou, Christos H.; Yannakakis, Mihalis 88 1993 On the hardness of approximating minimization problems. Zbl 1310.68094Lund, Carsten; Yannakakis, Mihalis 52 1993 The approximation of maximum subgraph problems. Zbl 1422.68087Lund, Carsten; Yannakakis, Mihalis 24 1993 Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 23 1993 Linear programming without the matrix. Zbl 1310.90073Papadimitriou, Christos H.; Yannakakis, Mihalis 14 1993 Computing the throughput of a network with dedicated lines. Zbl 0780.90041Papadimitriou, Christos H.; Serafini, Paolo; Yannakakis, Mihalis 2 1993 Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover. Zbl 1418.68244Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis 1 1993 Minimum and maximum delay problems in real-time systems. Zbl 0777.68045Courcoubetis, Costas; Yannakakis, Mihalis 20 1992 The analysis of local search problems and their heuristics. Zbl 0800.68854Yannakakis, Mihalis 2 1992 Suboptimal cuts: their enumeration, weight and number (extended abstract). Zbl 1427.68254Vazirani, Vijay V.; Yannakakis, Mihalis 1 1992 Optimization, approximation, and complexity classes. Zbl 0765.68036Papadimitriou, Christos H.; Yannakakis, Mihalis 400 1991 Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074Yannakakis, Mihalis 151 1991 Shortest paths without a map. Zbl 0733.68065Papadimitriou, Christos H.; Yannakakis, Mihalis 80 1991 Simple local search problems that are hard to solve. Zbl 0716.68048Schäffer, Alejandro A.; Yannakakis, Mihalis 48 1991 Memory efficient algorithms for the verification of temporal properties. Zbl 0786.68060Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M. 18 1991 High-probability parallel transitive-closure algorithms. Zbl 0716.68041Ullman, Jeffrey D.; Yannakakis, Mihalis 17 1991 Modularity of cycles and paths in graphs. Zbl 0799.68146Arkin, E. M.; Papadimitriou, C. H.; Yannakakis, M. 13 1991 Memory efficient algorithms for the verification of temporal properties. Zbl 0765.68120Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M. 9 1991 On the value of information in distributed decision-making (extended abstract). Zbl 1314.91068Papadimitriou, Christos H.; Yannakakis, Mihalis 8 1991 The input/output complexity of transitive closure. Zbl 0875.68239Ullman, Jeffrey D.; Yannakakis, Mihalis 5 1991 Batch sizing and job sequencing on a single machine. Zbl 0712.90035Coffman, E. G. jun.; Yannakakis, M.; Magazine, M. J.; Santos, C. 54 1990 Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032Papadimitriou, Christos H.; Yannakakis, Mihalis 34 1990 The analysis of local search problems and their heuristics. Zbl 0778.90058Yannakakis, Mihalis 11 1990 ...and 43 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 5,155 Authors 39 Paschos, Vangelis Th. 36 Heggernes, Pinar 32 Saurabh, Saket 30 Yannakakis, Mihalis 29 Chatterjee, Krishnendu 28 Monnot, Jérôme 27 Chandran, L. Sunil 26 Fomin, Fedor V. 26 Niedermeier, Rolf 25 Bazgan, Cristina 25 Golovach, Petr A. 25 Vardi, Moshe Ya’akov 24 Kratsch, Dieter 22 Villanger, Yngve 20 Fiorini, Samuel 19 Lokshtanov, Daniel 19 Pilipczuk, Michał 18 Escoffier, Bruno 18 Papadimitriou, Christos Harilaos 18 Pilipczuk, Marcin L. 18 van ’t Hof, Pim 17 Chen, Jian-er 17 Fernau, Henning 17 Malvestuto, Francesco Mario 16 Cao, Yixin 16 Cheng, Tai-Chiu Edwin 16 Demange, Marc 16 Ibaraki, Toshihide 16 Makino, Kazuhisa 16 Raman, Venkatesh 16 Thilikos, Dimitrios M. 15 Bentz, Cédric 15 Brandstädt, Andreas 14 Brázdil, Tomáš 14 de Figueiredo, Celina M. Herrera 14 Ekim, Tınaz 14 Faria, Luerbio 14 Gottlob, Georg 14 Kucera, Antonin 14 Lin, Guohui 14 Marx, Dániel 14 Nagamochi, Hiroshi 14 Sivadasan, Naveen 14 Vazirani, Vijay V. 13 Conforti, Michele 13 Cygan, Marek 13 Fujito, Toshihiro 13 Kovalyov, Mikhail Yakovlevich 13 Paulusma, Daniël 13 Wang, Lusheng 12 Baier, Christel 12 Bodlaender, Hans L. 12 Eiter, Thomas 12 Kanj, Iyad A. 12 Kloks, Ton 12 Komusiewicz, Christian 12 Kratsch, Stefan 12 Kwiatkowska, Marta Z. 12 Mishra, Sounaka 12 Papadopoulos, Charis 12 Paul, Christophe 12 Pokutta, Sebastian 12 Van Leeuwen, Erik Jan 11 Ausiello, Giorgio 11 Berry, Anne 11 Boros, Endre 11 Greco, Gianluigi 11 Guo, Jiong 11 Gurvich, Vladimir A. 11 Jansen, Klaus 11 Kiefer, Stefan 11 Kupferman, Orna 11 Lozin, Vadim Vladislavovich 11 Mahjoub, Ali Ridha 11 Panda, Bhawani Sankar 11 Spirakis, Paul G. 11 Szwarcfiter, Jayme Luiz 11 Tuza, Zsolt 11 Xiao, Mingyu 10 Corneil, Derek Gordon 10 Dragan, Feodor F. 10 Etessami, Kousha 10 Francis, Mathew C. 10 Halldórsson, Magnús Mar 10 Jiang, Tao 10 Kranakis, Evangelos Konstantinou 10 Lampis, Michael 10 Sau, Ignasi 10 Scarcello, Francesco 10 Shitov, Yaroslav Nikolaevich 10 Tiwary, Hans Raj 10 Woeginger, Gerhard Johannes 10 Yeo, Anders 9 Conte, Alessio 9 Costa, Marie-Christine 9 Creignou, Nadia 9 de Werra, Dominique 9 Demaine, Erik D. 9 Elbassioni, Khaled M. 9 Forejt, Vojtěch ...and 5,055 more Authors all top 5 Cited in 306 Serials 427 Theoretical Computer Science 362 Discrete Applied Mathematics 195 Information Processing Letters 179 Algorithmica 173 Journal of Computer and System Sciences 115 Discrete Mathematics 98 European Journal of Operational Research 86 Information and Computation 79 Mathematical Programming. Series A. Series B 75 Journal of Combinatorial Optimization 67 Artificial Intelligence 61 Theory of Computing Systems 54 Operations Research Letters 47 Journal of Discrete Algorithms 42 SIAM Journal on Computing 40 SIAM Journal on Discrete Mathematics 38 Discrete Optimization 37 Computers & Operations Research 36 Annals of Operations Research 29 Formal Methods in System Design 26 Journal of Graph Theory 25 Journal of Combinatorial Theory. Series B 23 Journal of Scheduling 22 Combinatorica 21 Networks 21 Order 21 International Journal of Foundations of Computer Science 20 Discrete & Computational Geometry 20 Computational Complexity 20 Annals of Mathematics and Artificial Intelligence 19 Acta Informatica 18 Computational Geometry 17 RAIRO. Operations Research 16 Journal of Global Optimization 16 International Journal of Computer Mathematics 16 Linear Algebra and its Applications 15 Mathematics of Operations Research 15 European Journal of Combinatorics 14 Graphs and Combinatorics 14 Discrete Mathematics, Algorithms and Applications 14 Computer Science Review 13 Information Sciences 13 International Journal of Approximate Reasoning 13 Formal Aspects of Computing 13 Distributed Computing 13 The Electronic Journal of Combinatorics 12 Machine Learning 12 Games and Economic Behavior 11 SIAM Journal on Algebraic and Discrete Methods 11 Annals of Pure and Applied Logic 11 Journal of Computer Science and Technology 11 Optimization Letters 11 Logical Methods in Computer Science 10 Applied Mathematics and Computation 10 Algorithms 9 Acta Mathematicae Applicatae Sinica. English Series 9 INFORMS Journal on Computing 9 RAIRO. Theoretical Informatics and Applications 9 4OR 9 Mathematical Programming Computation 8 International Journal of Computational Geometry & Applications 8 SIAM Journal on Optimization 8 Constraints 8 Journal of the ACM 7 Kybernetika 7 Operations Research 7 Journal of Automated Reasoning 7 Computational Statistics and Data Analysis 7 Computational Optimization and Applications 7 Journal of Graph Algorithms and Applications 6 Naval Research Logistics 6 Discussiones Mathematicae. Graph Theory 6 The Journal of Logic and Algebraic Programming 6 ACM Transactions on Computation Theory 6 Journal of Logical and Algebraic Methods in Programming 5 Computers & Mathematics with Applications 5 Computing 5 Fuzzy Sets and Systems 5 Journal of Combinatorial Theory. Series A 5 Journal of Optimization Theory and Applications 5 Mathematical Systems Theory 5 Mathematical Social Sciences 5 Optimization 5 Mathematical and Computer Modelling 5 SIAM Journal on Matrix Analysis and Applications 5 RAIRO. Informatique Théorique et Applications 5 ZOR. Zeitschrift für Operations Research 5 Cybernetics and Systems Analysis 5 Journal of Computer and Systems Sciences International 5 Journal of Mathematical Sciences (New York) 5 The Journal of Artificial Intelligence Research (JAIR) 5 Optimization Methods & Software 5 Theory and Practice of Logic Programming 5 JMMA. Journal of Mathematical Modelling and Algorithms 5 ACM Transactions on Computational Logic 4 Journal of Statistical Physics 4 BIT 4 Journal of Mathematical Psychology 4 Programming and Computer Software 4 Bulletin of the American Mathematical Society. New Series ...and 206 more Serials all top 5 Cited in 45 Fields 2,541 Computer science (68-XX) 1,472 Combinatorics (05-XX) 1,073 Operations research, mathematical programming (90-XX) 245 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 141 Mathematical logic and foundations (03-XX) 80 Convex and discrete geometry (52-XX) 79 Biology and other natural sciences (92-XX) 76 Order, lattices, ordered algebraic structures (06-XX) 75 Numerical analysis (65-XX) 65 Linear and multilinear algebra; matrix theory (15-XX) 61 Statistics (62-XX) 50 Information and communication theory, circuits (94-XX) 46 Probability theory and stochastic processes (60-XX) 41 Systems theory; control (93-XX) 13 Quantum theory (81-XX) 13 Statistical mechanics, structure of matter (82-XX) 9 Number theory (11-XX) 8 Manifolds and cell complexes (57-XX) 6 Geometry (51-XX) 6 General topology (54-XX) 5 Commutative algebra (13-XX) 5 Ordinary differential equations (34-XX) 5 Functional analysis (46-XX) 4 General and overarching topics; collections (00-XX) 4 Algebraic geometry (14-XX) 4 Group theory and generalizations (20-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 3 Associative rings and algebras (16-XX) 3 Approximations and expansions (41-XX) 3 Operator theory (47-XX) 3 Algebraic topology (55-XX) 3 Mechanics of particles and systems (70-XX) 2 General algebraic systems (08-XX) 2 Topological groups, Lie groups (22-XX) 2 Functions of a complex variable (30-XX) 2 Differential geometry (53-XX) 2 Mechanics of deformable solids (74-XX) 1 History and biography (01-XX) 1 Field theory and polynomials (12-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Measure and integration (28-XX) 1 Partial differential equations (35-XX) 1 Difference and functional equations (39-XX) 1 Integral transforms, operational calculus (44-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.