×

Yannakakis, Mihalis

Compute Distance To:
Author ID: yannakakis.mihalis Recent zbMATH articles by "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
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

Publications by Year

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.68036
Papadimitriou, 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.68062
Tarjan, Robert E.; Yannakakis, Mihalis
253
1984
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
183
1994
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
172
1988
The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029
Lewis, John M.; Yannakakis, Mihalis
168
1980
On the desirability of acyclic database schemes. Zbl 0624.68087
Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis
167
1983
Computing the minimum fill-in is NP-complete. Zbl 0496.68033
Yannakakis, Mihalis
166
1981
The complexity of the partial order dimension problem. Zbl 0516.06001
Yannakakis, Mihalis
160
1982
On the hardness of approximating minimization problems. Zbl 0814.68064
Lund, Carsten; Yannakakis, Mihalis
156
1994
Node-and edge-deletion NP-complete problems. Zbl 1282.68131
Yannakakis, Mihalis
152
1978
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
151
1991
Edge dominating sets in graphs. Zbl 0455.05047
Yannakakis, M.; Gavril, F.
134
1980
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
133
1988
Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075
Garg, N.; Vazirani, V. V.; Yannakakis, M.
104
1997
Node-deletion problems on bipartite graphs. Zbl 0468.05044
Yannakakis, M.
102
1981
The complexity of facets (and some facets of complexity). Zbl 0571.68028
Papadimitriou, C. H.; Yannakakis, M.
99
1984
The complexity of probabilistic verification. Zbl 0885.68109
Courcoubetis, Costas; Yannakakis, Mihalis
88
1995
The traveling salesman problem with distances one and two. Zbl 0778.90057
Papadimitriou, Christos H.; Yannakakis, Mihalis
88
1993
Shortest paths without a map. Zbl 0733.68065
Papadimitriou, Christos H.; Yannakakis, Mihalis
80
1991
Edge-deletion problems. Zbl 0468.05043
Yannakakis, Mihalis
70
1981
Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
66
1996
Embedding planar graphs in four pages. Zbl 0673.05022
Yannakakis, Mihalis
63
1989
Multiway cuts in node weighted graphs. Zbl 1068.68178
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
59
2004
Scheduling interval-ordered tasks. Zbl 0421.68040
Papadimitriou, C. H.; Yannakakis, M.
59
1979
Batch sizing and job sequencing on a single machine. Zbl 0712.90035
Coffman, E. G. jun.; Yannakakis, M.; Magazine, M. J.; Santos, C.
54
1990
On the hardness of approximating minimization problems. Zbl 1310.68094
Lund, Carsten; Yannakakis, Mihalis
52
1993
The maximum k-colorable subgraph problem for chordal graphs. Zbl 0653.68070
Yannakakis, Mihalis; Gavril, Fanica
51
1987
Simple local search problems that are hard to solve. Zbl 0716.68048
Schäffer, Alejandro A.; Yannakakis, Mihalis
48
1991
On the complexity of Nash equilibria and other fixed points. Zbl 1204.91003
Etessami, Kousha; Yannakakis, Mihalis
47
2010
The complexity of restricted spanning tree problems. Zbl 0478.68068
Papadimitriou, Christos H.; Yannakakis, Mihalis
46
1982
Markov decision processes and regular events. Zbl 0954.90061
Courcoubetis, Costas; Yannakakis, Mihalis
45
1998
Equivalences among relational expressions with the union and difference operators. Zbl 0456.68123
Sagiv, Yehoshua; Yannakakis, Mihalis
39
1980
A polynomial algorithm for the min-cut linear arrangement of trees. Zbl 0633.68063
Yannakakis, Mihalis
38
1985
On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031
Papadimitriou, Christos H.; Yannakakis, Mihalis
37
1996
Optimal scheduling of products with two subassemblies on a single machine. Zbl 0672.90075
Coffman, Edward G. jun.; Nozari, Ardavan; Yannakakis, Mihalis
36
1989
Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032
Papadimitriou, Christos H.; Yannakakis, Mihalis
34
1990
On the approximation of maximum satisfiability. Zbl 0820.68056
Yannakakis, Mihalis
31
1994
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1325.68091
Etessami, Kousha; Yannakakis, Mihalis
31
2009
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Zbl 0696.68076
Vazirani, Vijay V.; Yannakakis, Milhalis
30
1989
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
29
2003
Linear approximation of shortest superstrings. Zbl 0812.68075
Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis
29
1994
On the complexity of database queries. Zbl 0939.68024
Papadimitriou, Christos H.; Yannakakis, Mihalis
24
1999
On a class of totally unimodular matrices. Zbl 0565.90042
Yannakakis, Mihalis
24
1985
The approximation of maximum subgraph problems. Zbl 1422.68087
Lund, Carsten; Yannakakis, Mihalis
24
1993
Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
23
1993
A note on succinct representations of graphs. Zbl 0616.68041
Papadimitriou, Christos H.; Yannakakis, Mihalis
21
1986
Scheduling opposing forests. Zbl 0507.68021
Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M.
21
1983
Searching a fixed graph. Zbl 1045.90532
Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis
20
1996
The effect of a connectivity requirement on the complexity of maximum subgraph problems. Zbl 0421.68047
Yannakakis, 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.68055
Tarjan, Robert E.; Yannakakis, Mihalis
20
1985
Minimum and maximum delay problems in real-time systems. Zbl 0777.68045
Courcoubetis, Costas; Yannakakis, Mihalis
20
1992
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
18
1998
Memory efficient algorithms for the verification of temporal properties. Zbl 0786.68060
Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M.
18
1991
On complexity as bounded rationality (extended abstract). Zbl 1345.68216
Papadimitriou, Christos H.; Yannakakis, Mihalis
18
1994
Multi-objective model checking of Markov decision processes. Zbl 1161.68565
Etessami, Kousha; Kwiatkowska, Marta; Vardi, Moshe Y.; Yannakakis, Mihalis
17
2008
High-probability parallel transitive-closure algorithms. Zbl 0716.68041
Ullman, Jeffrey D.; Yannakakis, Mihalis
17
1991
Small approximate Pareto sets for biobjective shortest paths and other problems. Zbl 1198.90346
Diakonikolas, Ilias; Yannakakis, Mihalis
17
2009
Testing finite-state machines: state identification and verification. Zbl 1395.68173
Lee, David; Yannakakis, Mihalis
16
1994
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1118.68497
Etessami, Kousha; Yannakakis, Mihalis
16
2005
Recursive Markov decision processes and recursive stochastic games. Zbl 1085.68089
Etessami, Kousha; Yannakakis, Mihalis
16
2005
Distinguishing tests for nondeterministic and probabilistic machines. Zbl 0978.68522
Alur, Rajeev; Courcoubetis, Costas; Yannakakis, Mihalis
15
1995
On nested depth first search. Zbl 0880.68084
Holzmann, Gerard J.; Peled, Doron; Yannakakis, Mihalis
15
1997
Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042
Vazirani, Vijay V.; Yannakakis, Mihalis
14
2011
Efficiently computing succinct trade-off curves. Zbl 1080.90069
Vassilvitskii, Sergei; Yannakakis, Mihalis
14
2005
Linear programming without the matrix. Zbl 1310.90073
Papadimitriou, Christos H.; Yannakakis, Mihalis
14
1993
On the complexity of testing implications of functional and join dependencies. Zbl 0481.68094
Maier, David; Sagiv, Yehoshua; Yannakakis, Mihalis
13
1981
The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059
Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M.
13
1981
Algebraic dependencies. Zbl 0493.68095
Yannakakis, Mihalis; Papadimitriou, Christos H.
13
1982
Modularity of cycles and paths in graphs. Zbl 0799.68146
Arkin, 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.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
13
1999
Black box checking. Zbl 0952.68012
Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis
12
1999
Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
12
1994
Recursive concurrent stochastic games. Zbl 1133.91317
Etessami, Kousha; Yannakakis, Mihalis
12
2006
The analysis of local search problems and their heuristics. Zbl 0778.90058
Yannakakis, Mihalis
11
1990
Computational complexity. Zbl 0966.90506
Yannakakis, Mihalis
10
1997
Black box checking. Zbl 1046.68072
Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis
10
2002
Timing verification by successive approximation. Zbl 0939.68705
Alur, R.; Itai, A.; Kurshan, R. P.; Yannakakis, M.
10
1995
Testing the universal instance assumption. Zbl 0422.68048
Honeyman, Peter; Ladner, Richard E.; Yannakakis, Mihalis
10
1980
Permuting elements within columns of a matrix in order to minimize maximum row sum. Zbl 0551.90042
Coffman, E. G. jun.; Yannakakis, M.
10
1984
Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. Zbl 1286.68188
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
10
2012
Algorithmic verification of recursive probabilistic state machines. Zbl 1087.68054
Etessami, Kousha; Yannakakis, Mihalis
9
2005
Adaptive model checking. Zbl 1043.68570
Groce, Alex; Peled, Doron; Yannakakis, Mihalis
9
2002
Cutting and partitioning a graph after a fixed pattern. Zbl 0549.68062
Yannakakis, Mihalis; Kanellakis, Paris C.; Cosmadakis, Stavros S.; Papadimitriou, Christos H.
9
1983
Independent database schemas. Zbl 0603.68099
Graham, Marc H.; Yannakakis, Mihalis
9
1984
Memory efficient algorithms for the verification of temporal properties. Zbl 0765.68120
Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M.
9
1991
A theory of safe locking policies in database systems. Zbl 0488.68071
Yannakakis, Mihalis
9
1982
Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. Zbl 1272.68458
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
8
2012
Analysis of recursive state machines. Zbl 0991.68535
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
8
2001
Realizability and verification of MSC graphs. Zbl 1088.68097
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
8
2005
On recognizing integer polyhedra. Zbl 0718.68044
Papadimitriou, C. H.; Yannakakis, M.
8
1990
Markov decision processes and regular events. Zbl 0765.68152
Courcoubetis, Costas; Yannakakis, Mihalis
8
1990
Serializability by locking. Zbl 0631.68078
Yannakakis, Mihalis
8
1984
On the value of information in distributed decision-making (extended abstract). Zbl 1314.91068
Papadimitriou, Christos H.; Yannakakis, Mihalis
8
1991
Model checking of recursive probabilistic systems. Zbl 1351.68159
Etessami, Kousha; Yannakakis, Mihalis
8
2012
The complexity of non-monotone markets. Zbl 1293.91065
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
8
2013
Realizability and verification of MSC graphs. Zbl 0986.68518
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
7
2001
Recursive Markov decision processes and recursive stochastic games. Zbl 1333.91005
Etessami, Kousha; Yannakakis, Mihalis
7
2015
Tie-breaking semantics and structural totality. Zbl 0864.68028
Papadimitriou, Christos H.; Yannakakis, Mihalis
6
1997
Recursive stochastic games with positive rewards. Zbl 1153.91328
Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis
6
2008
Succinct approximate convex Pareto curves. Zbl 1192.90190
Diakonikolas, Ilias; Yannakakis, Mihalis
6
2008
Planar graphs that need four pages. Zbl 1448.05055
Yannakakis, Mihalis
2
2020
The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214
Chen, 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.60085
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
1
2018
On the complexity of simple and optimal deterministic mechanisms for an additive buyer. Zbl 1403.91163
Chen, Xi; Matikas, George; Paparas, Dimitris; Yannakakis, Mihalis
1
2018
The complexity of non-monotone markets. Zbl 1427.91130
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
3
2017
Doubly balanced connected graph partitioning. Zbl 1410.05172
Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil
1
2017
A polynomial time algorithm for computing extinction probabilities of multitype branching processes. Zbl 1378.68074
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
1
2017
How good is the Chord algorithm? Zbl 1344.68284
Daskalakis, Constantinos; Diakonikolas, Ilias; Yannakakis, Mihalis
1
2016
Recursive Markov decision processes and recursive stochastic games. Zbl 1333.91005
Etessami, Kousha; Yannakakis, Mihalis
7
2015
Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Zbl 1394.60084
Etessami, 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.68177
Stewart, 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.68309
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
1
2014
The complexity of non-monotone markets. Zbl 1293.91065
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
8
2013
Stochastic context-free grammars, regular languages, and newton’s method. Zbl 1334.68111
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
2
2013
Analysis of Boolean programs. Zbl 1381.68164
Godefroid, Patrice; Yannakakis, Mihalis
1
2013
Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. Zbl 1286.68188
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
10
2012
Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. Zbl 1272.68458
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
8
2012
Model checking of recursive probabilistic systems. Zbl 1351.68159
Etessami, Kousha; Yannakakis, Mihalis
8
2012
Market equilibrium under separable, piecewise-linear, concave utilities. Zbl 1327.91042
Vazirani, Vijay V.; Yannakakis, Mihalis
14
2011
Temporal synthesis for bounded systems and environments. Zbl 1230.68144
Kupferman, Orna; Lustig, Yoad; Vardi, Moshe Y.; Yannakakis, Mihalis
2
2011
On the complexity of Nash equilibria and other fixed points. Zbl 1204.91003
Etessami, Kousha; Yannakakis, Mihalis
47
2010
An impossibility theorem for price-adjustment mechanisms. Zbl 1205.91067
Papadimitriou, Christos H.; Yannakakis, Mihalis
3
2010
How good is the chord algorithm? Zbl 1288.68261
Daskalakis, Constantinos; Diakonikolas, Ilias; Yannakakis, Mihalis
2
2010
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1325.68091
Etessami, Kousha; Yannakakis, Mihalis
31
2009
Small approximate Pareto sets for biobjective shortest paths and other problems. Zbl 1198.90346
Diakonikolas, Ilias; Yannakakis, Mihalis
17
2009
Equilibria, fixed points, and complexity classes. Zbl 1302.68143
Yannakakis, Mihalis
4
2009
Computational aspects of equilibria. Zbl 1253.91004
Yannakakis, Mihalis
1
2009
Multi-objective model checking of Markov decision processes. Zbl 1161.68565
Etessami, Kousha; Kwiatkowska, Marta; Vardi, Moshe Y.; Yannakakis, Mihalis
17
2008
Recursive stochastic games with positive rewards. Zbl 1153.91328
Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis
6
2008
Succinct approximate convex Pareto curves. Zbl 1192.90190
Diakonikolas, Ilias; Yannakakis, Mihalis
6
2008
Recursive concurrent stochastic games. Zbl 1161.68619
Etessami, Kousha; Yannakakis, Mihalis
4
2008
Equilibria, fixed points, and complexity classes. Zbl 1259.68075
Yannakakis, Mihalis
2
2008
Multi-objective model checking of Markov decision processes. Zbl 1186.68286
Etessami, K.; Kwiatkowska, M.; Vardi, M. Y.; Yannakakis, M.
5
2007
Recursive concurrent stochastic games. Zbl 1133.91317
Etessami, Kousha; Yannakakis, Mihalis
12
2006
Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games. Zbl 1136.90499
Etessami, Kousha; Yannakakis, Mihalis
6
2006
Adaptive model checking. Zbl 1108.68073
Groce, Alex; Peled, Doron; Yannakakis, Mihalis
1
2006
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Zbl 1118.68497
Etessami, Kousha; Yannakakis, Mihalis
16
2005
Recursive Markov decision processes and recursive stochastic games. Zbl 1085.68089
Etessami, Kousha; Yannakakis, Mihalis
16
2005
Efficiently computing succinct trade-off curves. Zbl 1080.90069
Vassilvitskii, Sergei; Yannakakis, Mihalis
14
2005
Algorithmic verification of recursive probabilistic state machines. Zbl 1087.68054
Etessami, Kousha; Yannakakis, Mihalis
9
2005
Realizability and verification of MSC graphs. Zbl 1088.68097
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
8
2005
Multiway cuts in node weighted graphs. Zbl 1068.68178
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
59
2004
Efficiently computing succinct trade-off curves. Zbl 1099.90577
Vassilvitskii, Sergei; Yannakakis, Mihalis
5
2004
Testing, optimizaton, and games. Zbl 1099.68662
Yannakakis, Mihalis
2
2004
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
29
2003
Compression of partially ordered strings. Zbl 1274.68118
Alur, Rajeev; Chaudhuri, Swarat; Etessami, Kousha; Guha, Sudipto; Yannakakis, Mihalis
1
2003
Black box checking. Zbl 1046.68072
Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis
10
2002
Adaptive model checking. Zbl 1043.68570
Groce, Alex; Peled, Doron; Yannakakis, Mihalis
9
2002
Closed partition lattice and machine decomposition. Zbl 1392.68270
Lee, David; Yannakakis, Mihalis
1
2002
Analysis of recursive state machines. Zbl 0991.68535
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
8
2001
Realizability and verification of MSC graphs. Zbl 0986.68518
Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis
7
2001
Approximation of multiobjective optimization problems. Zbl 0997.68563
Yannakakis, Mihalis
1
2001
On the complexity of database queries. Zbl 0939.68024
Papadimitriou, Christos H.; Yannakakis, Mihalis
24
1999
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
13
1999
Black box checking. Zbl 0952.68012
Peled, Doron; Vardi, Moshe Y.; Yannakakis, Mihalis
12
1999
A convex relaxation for the asymmetric TSP. Zbl 1008.90519
Vempala, Santosh; Yannakakis, Mihalis
3
1999
Markov decision processes and regular events. Zbl 0954.90061
Courcoubetis, Costas; Yannakakis, Mihalis
45
1998
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
18
1998
Primal-dual approximation algorithms for integral flow and multicut in trees. Zbl 0873.68075
Garg, N.; Vazirani, V. V.; Yannakakis, M.
104
1997
On nested depth first search. Zbl 0880.68084
Holzmann, Gerard J.; Peled, Doron; Yannakakis, Mihalis
15
1997
Computational complexity. Zbl 0966.90506
Yannakakis, Mihalis
10
1997
Tie-breaking semantics and structural totality. Zbl 0864.68028
Papadimitriou, Christos H.; Yannakakis, Mihalis
6
1997
Approximate max-flow min-(multi)cut theorems and their applications. Zbl 0844.68061
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
66
1996
On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031
Papadimitriou, Christos H.; Yannakakis, Mihalis
37
1996
Searching a fixed graph. Zbl 1045.90532
Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis
20
1996
The complexity of probabilistic verification. Zbl 0885.68109
Courcoubetis, Costas; Yannakakis, Mihalis
88
1995
Distinguishing tests for nondeterministic and probabilistic machines. Zbl 0978.68522
Alur, Rajeev; Courcoubetis, Costas; Yannakakis, Mihalis
15
1995
Timing verification by successive approximation. Zbl 0939.68705
Alur, R.; Itai, A.; Kurshan, R. P.; Yannakakis, M.
10
1995
On datalog vs polynomial time. Zbl 0831.68015
Afrati, Foto; Cosmandakis, Stavros S.; Yannakakis, Mihalis
5
1995
Testing finite state machines: Fault detection. Zbl 0826.68044
Yannakakis, Mihalis; Lee, David
3
1995
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
183
1994
On the hardness of approximating minimization problems. Zbl 0814.68064
Lund, Carsten; Yannakakis, Mihalis
156
1994
On the approximation of maximum satisfiability. Zbl 0820.68056
Yannakakis, Mihalis
31
1994
Linear approximation of shortest superstrings. Zbl 0812.68075
Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis
29
1994
On complexity as bounded rationality (extended abstract). Zbl 1345.68216
Papadimitriou, Christos H.; Yannakakis, Mihalis
18
1994
Testing finite-state machines: state identification and verification. Zbl 1395.68173
Lee, David; Yannakakis, Mihalis
16
1994
Multiway cuts in directed and node weighted graphs (extended abstract). Zbl 1418.68168
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
12
1994
The traveling salesman problem with distances one and two. Zbl 0778.90057
Papadimitriou, Christos H.; Yannakakis, Mihalis
88
1993
On the hardness of approximating minimization problems. Zbl 1310.68094
Lund, Carsten; Yannakakis, Mihalis
52
1993
The approximation of maximum subgraph problems. Zbl 1422.68087
Lund, Carsten; Yannakakis, Mihalis
24
1993
Approximate MAX-flow MIN-(multi)cut theorems and their applications. Zbl 1310.05198
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
23
1993
Linear programming without the matrix. Zbl 1310.90073
Papadimitriou, Christos H.; Yannakakis, Mihalis
14
1993
Computing the throughput of a network with dedicated lines. Zbl 0780.90041
Papadimitriou, 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.68244
Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis
1
1993
Minimum and maximum delay problems in real-time systems. Zbl 0777.68045
Courcoubetis, Costas; Yannakakis, Mihalis
20
1992
The analysis of local search problems and their heuristics. Zbl 0800.68854
Yannakakis, Mihalis
2
1992
Suboptimal cuts: their enumeration, weight and number (extended abstract). Zbl 1427.68254
Vazirani, Vijay V.; Yannakakis, Mihalis
1
1992
Optimization, approximation, and complexity classes. Zbl 0765.68036
Papadimitriou, Christos H.; Yannakakis, Mihalis
400
1991
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
151
1991
Shortest paths without a map. Zbl 0733.68065
Papadimitriou, Christos H.; Yannakakis, Mihalis
80
1991
Simple local search problems that are hard to solve. Zbl 0716.68048
Schäffer, Alejandro A.; Yannakakis, Mihalis
48
1991
Memory efficient algorithms for the verification of temporal properties. Zbl 0786.68060
Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M.
18
1991
High-probability parallel transitive-closure algorithms. Zbl 0716.68041
Ullman, Jeffrey D.; Yannakakis, Mihalis
17
1991
Modularity of cycles and paths in graphs. Zbl 0799.68146
Arkin, E. M.; Papadimitriou, C. H.; Yannakakis, M.
13
1991
Memory efficient algorithms for the verification of temporal properties. Zbl 0765.68120
Courcoubetis, C.; Vardi, M.; Wolper, P.; Yannakakis, M.
9
1991
On the value of information in distributed decision-making (extended abstract). Zbl 1314.91068
Papadimitriou, Christos H.; Yannakakis, Mihalis
8
1991
The input/output complexity of transitive closure. Zbl 0875.68239
Ullman, Jeffrey D.; Yannakakis, Mihalis
5
1991
Batch sizing and job sequencing on a single machine. Zbl 0712.90035
Coffman, E. G. jun.; Yannakakis, M.; Magazine, M. J.; Santos, C.
54
1990
Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032
Papadimitriou, Christos H.; Yannakakis, Mihalis
34
1990
The analysis of local search problems and their heuristics. Zbl 0778.90058
Yannakakis, Mihalis
11
1990
...and 43 more Documents
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.