| Year |
Citation |
Score |
| 2020 |
Soltan S, Yannakakis M, Zussman G. Doubly Balanced Connected Graph Partitioning Acm Transactions On Algorithms. 16: 1-24. DOI: 10.1145/3381419 |
0.321 |
|
| 2020 |
Yannakakis M. Planar graphs that need four pages Journal of Combinatorial Theory, Series B. 145: 241-263. DOI: 10.1016/J.Jctb.2020.05.008 |
0.331 |
|
| 2018 |
Soltan S, Yannakakis M, Zussman G. Power Grid State Estimation Following a Joint Cyber and Physical Attack Ieee Transactions On Control of Network Systems. 5: 499-512. DOI: 10.1109/Tcns.2016.2620807 |
0.334 |
|
| 2018 |
Chen X, Diakonikolas I, Paparas D, Sun X, Yannakakis M. The complexity of optimal multidimensional pricing for a unit-demand buyer Games and Economic Behavior. 110: 139-164. DOI: 10.1016/J.Geb.2018.03.016 |
0.723 |
|
| 2017 |
Etessami K, Stewart A, Yannakakis M. A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes Siam Journal On Computing. 46: 1515-1553. DOI: 10.1137/16M105678X |
0.374 |
|
| 2015 |
Stewart A, Etessami K, Yannakakis M. Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata Journal of the Acm. 62. DOI: 10.1145/2789208 |
0.412 |
|
| 2015 |
Etessami K, Yannakakis M. Recursive Markov decision processes and recursive stochastic games Journal of the Acm. 62. DOI: 10.1145/2699431 |
0.478 |
|
| 2015 |
Chen X, Diakonikolas I, Orfanou A, Paparas D, Sun X, Yannakakis M. On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2015: 1464-1479. DOI: 10.1109/FOCS.2015.93 |
0.7 |
|
| 2015 |
Etessami K, Stewart A, Yannakakis M. Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9135: 184-196. DOI: 10.1016/J.Ic.2018.02.013 |
0.435 |
|
| 2014 |
Etessami K, Stewart A, Yannakakis M. A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing Acm Transactions On Computation Theory. 6. DOI: 10.1145/2601327 |
0.444 |
|
| 2014 |
Chen X, Diakonikolas I, Paparas D, Sun X, Yannakakis M. The complexity of optimal multidimensional pricing Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1319-1328. |
0.71 |
|
| 2012 |
Etessami K, Stewart A, Yannakakis M. Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7391: 314-326. DOI: 10.1287/Moor.2018.0970 |
0.422 |
|
| 2012 |
Etessami K, Stewart A, Yannakakis M. Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars Proceedings of the Annual Acm Symposium On Theory of Computing. 579-588. DOI: 10.1145/2213977.2214030 |
0.31 |
|
| 2012 |
Etessami K, Yannakakis M. Model checking of recursive probabilistic systems Acm Transactions On Computational Logic. 13. DOI: 10.1145/2159531.2159534 |
0.48 |
|
| 2012 |
Yannakakis M. Computation of least fixed points Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7464: 63. DOI: 10.1007/978-3-642-32589-2_8 |
0.321 |
|
| 2011 |
Vazirani VV, Yannakakis M. Market equilibrium under separable, piecewise-linear, concave utilities Journal of the Acm. 58. DOI: 10.1145/1970392.1970394 |
0.314 |
|
| 2010 |
Daskalakis C, Diakonikolas I, Yannakakis M. How good is the Chord algorithm? Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 978-991. DOI: 10.1137/13093875X |
0.694 |
|
| 2010 |
Etessami K, Yannakakis M. On the complexity of Nash equilibria and other fixed points Siam Journal On Computing. 39: 2531-2597. DOI: 10.1137/080720826 |
0.484 |
|
| 2010 |
Etessami K, Wojtczak D, Yannakakis M. Quasi-birth-death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems Performance Evaluation. 67: 837-857. DOI: 10.1016/J.Peva.2009.12.009 |
0.462 |
|
| 2009 |
Etessami K, Yannakakis M. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations Journal of the Acm. 56. DOI: 10.1145/1462153.1462154 |
0.484 |
|
| 2009 |
Diakonikolas I, Yannakakis M. Small approximate pareto sets for biobjective shortest paths and other problems Siam Journal On Computing. 39: 1340-1371. DOI: 10.1137/080724514 |
0.734 |
|
| 2008 |
Etessami K, Kwiatkowska M, Vardi MY, Yannakakis M. Multi-objective model checking of Markov decision processes Logical Methods in Computer Science. 4. DOI: 10.2168/Lmcs-4(4:8)2008 |
0.455 |
|
| 2008 |
Etessami K, Yannakakis M. Recursive concurrent stochastic games Logical Methods in Computer Science. 4. DOI: 10.2168/Lmcs-4(4:7)2008 |
0.431 |
|
| 2008 |
Etessami K, Wojtczak D, Yannakakis M. Recursive stochastic games with positive rewards Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5125: 711-723. DOI: 10.1016/J.Tcs.2018.12.018 |
0.415 |
|
| 2008 |
Diakonikolas I, Yannakakis M. Succinct approximate convex Pareto curves (extended abstract) Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 74-83. |
0.725 |
|
| 2007 |
Diakonikolas I, Yannakakis M. Small approximate pareto sets for bi-objective shortest paths and other problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4627: 74-88. |
0.72 |
|
| 2006 |
Etessami K, Yannakakis M. Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3884: 634-645. DOI: 10.1007/11672142_52 |
0.359 |
|
| 2005 |
Alur R, Benedikt M, Etessami K, Godefroid P, Reps T, Yannakakis M. Analysis of recursive state machines Acm Transactions On Programming Languages and Systems. 27: 786-818. DOI: 10.1145/1075382.1075387 |
0.346 |
|
| 2005 |
Vassilvitskii S, Yannakakis M. Efficiently computing succinct trade-off curves Theoretical Computer Science. 348: 334-356. DOI: 10.1016/j.tcs.2005.09.022 |
0.396 |
|
| 2005 |
Etessami K, Yannakakis M. Algorithmic verification of recursive probabilistic state machines Lecture Notes in Computer Science. 3440: 253-270. |
0.326 |
|
| 2004 |
Garg N, Vazirani VV, Yannakakis M. Multiway cuts in node weighted graphs Journal of Algorithms. 50: 49-61. DOI: 10.1016/S0196-6774(03)00111-1 |
0.419 |
|
| 2003 |
Guruswami V, Khanna S, Rajaraman R, Shepherd B, Yannakakis M. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems Journal of Computer and System Sciences. 67: 473-496. DOI: 10.1016/S0022-0000(03)00066-7 |
0.452 |
|
| 2002 |
Coffman EG, Courcoubetis C, Garey MR, Johnson DS, Shor PW, Weber RR, Yannakakis M. Perfect packing theorems and the average-case behavior of optimal and online bin packing Siam Review. 44: 95-108. DOI: 10.1137/S0036144501395423 |
0.328 |
|
| 2001 |
Alur R, Yannakakis M. Model checking of hierarchical state machines Acm Transactions On Programming Languages and Systems. 23: 273-303. DOI: 10.1145/503502.503503 |
0.331 |
|
| 2001 |
Yannakakis M. Approximation of multiobjective optimization problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2125. DOI: 10.1007/3-540-44634-6_1 |
0.387 |
|
| 2000 |
Coffman EG, Courcoubetis C, Garey MR, Johnson DS, Shor PW, Weber RR, Yannakakis M. Bin packing with discrete item sizes, part I: perfect packing theorems and the average case behavior of optimal packings Siam Journal On Discrete Mathematics. 13: 384-402. DOI: 10.1137/S0895480197325936 |
0.307 |
|
| 2000 |
Papadimitriou CH, Yannakakis M. On the approximability of trade-offs and optimal access of web sources Annual Symposium On Foundations of Computer Science - Proceedings. 86-92. |
0.358 |
|
| 1999 |
Alur R, Yannakakis M. Model checking of message sequence charts Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1664: 114-129. |
0.318 |
|
| 1999 |
Vempala S, Yannakakis M. Convex relaxation for the asymmetric TSP Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. S975-S976. |
0.325 |
|
| 1998 |
Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M. On the complexity of protein folding Journal of Computational Biology. 5: 423-465. PMID 9773342 DOI: 10.1089/Cmb.1998.5.423 |
0.313 |
|
| 1998 |
Kupferman O, Kurshan RP, Yannakakis M. Existence of reduction hierarchies Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1414: 327-340. DOI: 10.1007/BFb0028023 |
0.34 |
|
| 1997 |
Garg N, Vazirani VV, Yannakakis M. Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees Algorithmica (New York). 18: 3-20. DOI: 10.1007/Bf02523685 |
0.418 |
|
| 1996 |
Garg N, Vazirani VV, Yannakakis M. Approximate max-flow min-(multi)cut theorems and their applications Siam Journal On Computing. 25: 235-251. DOI: 10.1137/S0097539793243016 |
0.333 |
|
| 1996 |
Papadimitriou CH, Yannakakis M. On limited nondeterminism and the complexity of the V-C dimension Journal of Computer and System Sciences. 53: 161-170. DOI: 10.1006/Jcss.1996.0058 |
0.453 |
|
| 1996 |
Koutsoupias E, Papadimitriou C, Yannakakis M. Searching a fixed graph Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1099: 280-289. |
0.327 |
|
| 1995 |
Courcoubetis C, Yannakakis M. The complexity of probabilistic verification Journal of the Acm (Jacm). 42: 857-907. DOI: 10.1145/210332.210339 |
0.376 |
|
| 1995 |
Yannakakis M, Lee D. Testing finite state machines: Fault detection Journal of Computer and System Sciences. 50: 209-227. DOI: 10.1006/Jcss.1995.1019 |
0.337 |
|
| 1994 |
Lund C, Yannakakis M. On the hardness of approximating minimization problems Journal of the Acm. 41: 960-981. DOI: 10.1145/185675.306789 |
0.456 |
|
| 1994 |
Blum A, Jiang T, Li M, Tromp J, Yannakakis M. Linear approximation of shortest superstrings Journal of the Acm. 41: 630-647. DOI: 10.1145/179812.179818 |
0.443 |
|
| 1994 |
Dahlhaus E, Johnson DS, Papadimitriou CH, Seymour PD, Yannakakis M. The Complexity of Multiterminal Cuts Siam Journal On Computing. 23: 864-894. DOI: 10.1137/S0097539792225297 |
0.451 |
|
| 1994 |
Yannakakis M. On the Approximation of Maximum Satisfiability Journal of Algorithms. 17: 475-502. DOI: 10.1006/jagm.1994.1045 |
0.315 |
|
| 1994 |
Dahlhaus E, Johnson DS, Papadimitriou CH, Seymour PD, Yannakakis M. Complexity of multiterminal cuts Siam Journal On Computing. 23: 864-894. |
0.348 |
|
| 1994 |
Papadimitriou CH, Yannakakis M. On complexity as bounded rationality Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 726-733. |
0.304 |
|
| 1993 |
Papadimitriou CH, Yannakakis M. The Traveling Salesman Problem with Distances One and Two Mathematics of Operations Research. 18: 1-11. DOI: 10.1287/Moor.18.1.1 |
0.443 |
|
| 1992 |
Courcoubetis C, Vardi M, Wolper P, Yannakakis M. Memory-efficient algorithms for the verification of temporal properties Formal Methods in System Design. 1: 275-288. DOI: 10.1007/BF00121128 |
0.312 |
|
| 1992 |
Dahlhaus E, Johnson DS, Papadimitriou CH, Seymour PD, Yannakakis M. Complexity of multiway cuts Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 241-251. |
0.348 |
|
| 1991 |
Arkin EM, Papadimitriou CH, Yannakakis M. Modularity of cycles and paths in graphs Journal of the Acm. 38: 255-274. DOI: 10.1145/103516.103517 |
0.382 |
|
| 1991 |
Ullman JD, Yannakakis M. High-Probability Parallel Transitive-Closure Algorithms Siam Journal On Computing. 20: 100-125. DOI: 10.1137/0220006 |
0.615 |
|
| 1991 |
Papadimitriou CH, Yannakakis M. Shortest paths without a map Theoretical Computer Science. 84: 127-150. DOI: 10.1016/0304-3975(91)90263-2 |
0.443 |
|
| 1991 |
Yannakakis M. Expressing combinatorial optimization problems by Linear Programs Journal of Computer and System Sciences. 43: 441-466. DOI: 10.1016/0022-0000(91)90024-Y |
0.45 |
|
| 1991 |
Papadimitriou CH, Yannakakis M. Optimization, approximation, and complexity classes Journal of Computer and System Sciences. 43: 425-440. DOI: 10.1016/0022-0000(91)90023-X |
0.47 |
|
| 1991 |
Ullman JD, Yannakakis M. The input/output complexity of transitive closure Annals of Mathematics and Artificial Intelligence. 3: 331-360. DOI: 10.1007/Bf01530929 |
0.593 |
|
| 1990 |
Papadimitriou CH, Yannakakis M. Towards an Architecture-Independent Analysis of Parallel Algorithms Siam Journal On Computing. 19: 322-328. DOI: 10.1137/0219021 |
0.383 |
|
| 1990 |
Coffman EG, Yannakakis M, Magazine MJ, Santos C. Batch sizing and job sequencing on a single machine Annals of Operations Research. 26: 135-147. DOI: 10.1007/Bf02248589 |
0.429 |
|
| 1990 |
Papadimitriou CH, Yannakakis M. On recognizing integer polyhedra Combinatorica. 10: 107-109. DOI: 10.1007/Bf02122701 |
0.364 |
|
| 1989 |
Coffman EG, Nozari A, Yannakakis M. Optimal Scheduling of Products with Two Subassemblies on a Single Machine Operations Research. 37: 426-436. DOI: 10.1287/Opre.37.3.426 |
0.311 |
|
| 1989 |
Vazirani VV, Yannakakis M. Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs Discrete Applied Mathematics. 25: 179-190. DOI: 10.1016/0166-218X(89)90053-X |
0.372 |
|
| 1988 |
Johnson DS, Yannakakis M, Papadimitriou CH. On generating all maximal independent sets Information Processing Letters. 27: 119-123. DOI: 10.1016/0020-0190(88)90065-8 |
0.31 |
|
| 1987 |
Papadimitriou CH, Yannakakis M. The Complexity of Reliable Concurrency Control Siam Journal On Computing. 16: 538-553. DOI: 10.1137/0216036 |
0.315 |
|
| 1987 |
Yannakakis M, Gavril F. The maximum k-colorable subgraph problem for chordal graphs Information Processing Letters. 24: 133-137. DOI: 10.1016/0020-0190(87)90107-4 |
0.406 |
|
| 1986 |
Papadimitriou CH, Yannakakis M. A note on succinct representations of graphs Information and Control. 71: 181-185. DOI: 10.1016/S0019-9958(86)80009-2 |
0.367 |
|
| 1986 |
Wolfson O, Yannakakis M. Deadlock-freedom (and safety) of transactions in a distributed database Journal of Computer and System Sciences. 33: 161-178. DOI: 10.1016/0022-0000(86)90017-6 |
0.46 |
|
| 1985 |
Yannakakis M. On a Class of Totally Unimodular Matrices Mathematics of Operations Research. 10: 280-304. DOI: 10.1287/Moor.10.2.280 |
0.433 |
|
| 1985 |
Yannakakis M. A polynomial algorithm for the min-cut linear arrangement of trees Journal of the Acm (Jacm). 32: 950-988. DOI: 10.1145/4221.4228 |
0.352 |
|
| 1984 |
Coffman EG, Yannakakis M. PERMUTING ELEMENTS WITHIN COLUMNS OF A MATRIX IN ORDER TO MINIMIZE MAXIMUM ROW SUM Mathematics of Operations Research. 9: 384-390. DOI: 10.1287/Moor.9.3.384 |
0.421 |
|
| 1984 |
Yannakakis M. Serializability by Locking Journal of the Acm (Jacm). 31: 227-244. DOI: 10.1145/62.322425 |
0.375 |
|
| 1984 |
Tarjan RE, Yannakakis M. Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs Siam Journal On Computing. 13: 566-579. DOI: 10.1137/0213035 |
0.386 |
|
| 1984 |
Graham MH, Yannakakis M. Independent database schemas Journal of Computer and System Sciences. 28: 121-141. DOI: 10.1016/0022-0000(84)90079-5 |
0.402 |
|
| 1983 |
Beeri C, Fagin R, Maier D, Yannakakis M. On the Desirability of Acyclic Database Schemes Journal of the Acm (Jacm). 30: 479-513. DOI: 10.1145/2402.322389 |
0.346 |
|
| 1983 |
Garey MR, Johnson DS, Tarjan RE, Yannakakis M. Scheduling Opposing Forests Siam Journal On Algebraic Discrete Methods. 4: 72-93. DOI: 10.1137/0604011 |
0.439 |
|
| 1983 |
Fagin R, Maier D, Ullman JD, Yannakakis M. Tools for Template Dependencies Siam Journal On Computing. 12: 36-59. DOI: 10.1137/0212003 |
0.562 |
|
| 1982 |
Papadimitriou CH, Yannakakis M. The complexity of restricted spanning tree problems Journal of the Acm (Jacm). 29: 285-309. DOI: 10.1145/322307.322309 |
0.383 |
|
| 1982 |
Yannakakis M. The Complexity of the Partial Order Dimension Problem Siam Journal On Algebraic Discrete Methods. 3: 351-358. DOI: 10.1137/0603036 |
0.411 |
|
| 1982 |
Aho AV, Wyner AD, Yannakakis M, Ullman JD. Bounds on the size and transmission rate of communications protocols Computers and Mathematics With Applications. 8: 205-214. DOI: 10.1016/0898-1221(82)90043-8 |
0.531 |
|
| 1981 |
Yannakakis M. Computing the Minimum Fill-In is NP-Complete Siam Journal On Algebraic Discrete Methods. 2: 77-79. DOI: 10.1137/0602010 |
0.445 |
|
| 1981 |
Yannakakis M. Node-Deletion Problems on Bipartite Graphs Siam Journal On Computing. 10: 310-327. DOI: 10.1137/0210022 |
0.441 |
|
| 1981 |
Yannakakis M. Edge-Deletion Problems Siam Journal On Computing. 10: 297-309. DOI: 10.1137/0210021 |
0.456 |
|
| 1981 |
Papadimitriou CH, Yannakakis M. On minimal Eulerian graphs Information Processing Letters. 12: 203-205. DOI: 10.1016/0020-0190(81)90102-2 |
0.342 |
|
| 1981 |
Blum M, Karp RM, Vornberger O, Papadimitriu CH, Yannakakis M. The complexity of testing whether a graph is a superconcentrator Information Processing Letters. 13: 164-167. DOI: 10.1016/0020-0190(81)90050-8 |
0.332 |
|
| 1981 |
Papadimitriou CH, Yannakakis M. The clique problem for planar graphs Information Processing Letters. 13: 131-133. DOI: 10.1016/0020-0190(81)90041-7 |
0.419 |
|
| 1980 |
Yannakakis M, Gavril F. Edge Dominating Sets in Graphs Siam Journal On Applied Mathematics. 38: 364-372. DOI: 10.1137/0138030 |
0.447 |
|
| 1980 |
Lewis JM, Yannakakis M. The node-deletion problem for hereditary properties is NP-complete Journal of Computer and System Sciences. 20: 219-230. DOI: 10.1016/0022-0000(80)90060-4 |
0.411 |
|
| 1980 |
Honeyman P, Ladner RE, Yannakakis M. Testing the universal instance assumption Information Processing Letters. 10: 14-19. DOI: 10.1016/0020-0190(80)90114-3 |
0.639 |
|
| 1979 |
Sagiv Y, Yannakakis M. EQUIVALENCE AMONG RELATIONAL EXPRESSIONS WITH THE UNION AND DIFFERENCE OPERATIONS . 535-548. DOI: 10.1145/322217.322221 |
0.42 |
|
| 1979 |
Yannakakis M. The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems Journal of the Acm (Jacm). 26: 618-630. DOI: 10.1145/322154.322157 |
0.423 |
|
| 1979 |
Papadimitriou CH, Yannakakis M. Scheduling Interval-Ordered Tasks Siam Journal On Computing. 8: 405-409. DOI: 10.1137/0208031 |
0.321 |
|
| 1979 |
Yannakakis M, Pavlidis T. Topological characterization of families of graphs generated by certain types of graph grammars Information and Control. 42: 72-86. DOI: 10.1016/S0019-9958(79)90173-6 |
0.351 |
|
| 1979 |
Aho AV, Ullman JD, Yannakakis M. MODELING COMMUNICATIONS PROTOCOLS BY AUTOMATA Annual Symposium On Foundations of Computer Science - Proceedings. 267-273. |
0.482 |
|
| Show low-probability matches. |
