dblp.uni-trier.dewww.uni-trier.de

Mihalis Yannakakis Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
194EEMihalis Yannakakis: Computational Aspects of Equilibria. SAGT 2009: 2-13
193EEKousha Etessami, Mihalis Yannakakis: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1): (2009)
2008
192EEMihalis Yannakakis: Automata, Probability, and Recursion. CIAA 2008: 23-32
191EEKousha Etessami, Dominik Wojtczak, Mihalis Yannakakis: Recursive Stochastic Games with Positive Rewards. ICALP (1) 2008: 711-723
190EEKousha Etessami, Dominik Wojtczak, Mihalis Yannakakis: Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. QEST 2008: 243-253
189EEIlias Diakonikolas, Mihalis Yannakakis: Succinct approximate convex pareto curves. SODA 2008: 74-83
188EEMihalis Yannakakis: Equilibria, Fixed Points, and Complexity Classes. STACS 2008: 19-38
187EEMihalis Yannakakis: Equilibria, Fixed Points, and Complexity Classes CoRR abs/0802.2831: (2008)
186EEIlias Diakonikolas, Mihalis Yannakakis: Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems CoRR abs/0805.2646: (2008)
185EEKousha Etessami, Mihalis Yannakakis: Recursive Concurrent Stochastic Games CoRR abs/0810.3581: (2008)
184EEKousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis: Multi-Objective Model Checking of Markov Decision Processes CoRR abs/0810.5728: (2008)
183EEKousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis: Multi-Objective Model Checking of Markov Decision Processes. Logical Methods in Computer Science 4(4): (2008)
182EEKousha Etessami, Mihalis Yannakakis: Recursive Concurrent Stochastic Games. Logical Methods in Computer Science 4(4): (2008)
2007
181EEIlias Diakonikolas, Mihalis Yannakakis: Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. APPROX-RANDOM 2007: 74-88
180EEKousha Etessami, Mihalis Yannakakis: On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). FOCS 2007: 113-123
179EEKousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis: Multi-objective Model Checking of Markov Decision Processes. TACAS 2007: 50-65
2006
178EEMihalis Yannakakis: Analysis of Recursive Probabilistic Models. ATVA 2006: 1-5
177EEKousha Etessami, Mihalis Yannakakis: Recursive Concurrent Stochastic Games. ICALP (2) 2006: 324-335
176EEMihalis Yannakakis: Recursion and Probability. IFIP TCS 2006: 13
175EEGuoqiang Shu, David Lee, Mihalis Yannakakis: A note on broadcast encryption key management with applications to large scale emergency alert systems. IPDPS 2006
174EEKousha Etessami, Mihalis Yannakakis: Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. STACS 2006: 634-645
173EEMihalis Yannakakis: Succinct Approximation of Trade-Off Curves. WINE 2006: 149
172EEAlex Groce, Doron Peled, Mihalis Yannakakis: Adaptive Model Checking. Logic Journal of the IGPL 14(5): 729-744 (2006)
2005
171EEKousha Etessami, Mihalis Yannakakis: Recursive Markov Decision Processes and Recursive Stochastic Games. ICALP 2005: 891-903
170EEKousha Etessami, Mihalis Yannakakis: Probability and Recursion. ISAAC 2005: 2-4
169EEMihalis Yannakakis, Kousha Etessami: Checking LTL Properties of Recursive Markov Chains. QEST 2005: 155-165
168EEDamon Mosk-Aoyama, Mihalis Yannakakis: Testing hierarchical systems. SODA 2005: 1126-1135
167EEKousha Etessami, Mihalis Yannakakis: Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. STACS 2005: 340-352
166EEKousha Etessami, Mihalis Yannakakis: Algorithmic Verification of Recursive Probabilistic State Machines. TACAS 2005: 253-270
165EERajeev Alur, Michael Benedikt, Kousha Etessami, Patrice Godefroid, Thomas W. Reps, Mihalis Yannakakis: Analysis of recursive state machines. ACM Trans. Program. Lang. Syst. 27(4): 786-818 (2005)
164EERajeev Alur, Kousha Etessami, Mihalis Yannakakis: Realizability and verification of MSC graphs. Theor. Comput. Sci. 331(1): 97-114 (2005)
163EESergei Vassilvitskii, Mihalis Yannakakis: Efficiently computing succinct trade-off curves. Theor. Comput. Sci. 348(2-3): 334-356 (2005)
2004
162EESergei Vassilvitskii, Mihalis Yannakakis: Efficiently Computing Succinct Trade-Off Curves. ICALP 2004: 1201-1213
161EEMihalis Yannakakis: Testing, Optimizaton, and Games. ICALP 2004: 28-45
160EEMihalis Yannakakis: Testing, Optimizaton, and Games. LICS 2004: 78-88
159EEDavid Lee, Christine Liu, Mihalis Yannakakis: Protocol System Integration, Interface and Interoperability. OPODIS 2004: 1-19
158EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway cuts in node weighted graphs. J. Algorithms 50(1): 49-61 (2004)
157EESampath Kannan, Mihalis Yannakakis: Guest Editors' foreword. J. Comput. Syst. Sci. 68(2): 237 (2004)
2003
156EERajeev Alur, Swarat Chaudhuri, Kousha Etessami, Sudipto Guha, Mihalis Yannakakis: Compression of Partially Ordered Strings. CONCUR 2003: 42-56
155EERajeev Alur, Kousha Etessami, Mihalis Yannakakis: Inference of Message Sequence Charts. IEEE Trans. Software Eng. 29(7): 623-633 (2003)
154EEVenkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3): 473-496 (2003)
2002
153EEAlex Groce, Doron Peled, Mihalis Yannakakis: AMC: An Adaptive Model Checker. CAV 2002: 521-525
152EEMihalis Yannakakis: Testing and Checking of Finite State Systems. LATIN 2002: 14
151EEAlex Groce, Doron Peled, Mihalis Yannakakis: Adaptive Model Checking. TACAS 2002: 357-370
150EEDavid Lee, Mihalis Yannakakis: Closed Partition Lattice and Machine Decomposition. IEEE Trans. Computers 51(2): 216-228 (2002)
149 Doron Peled, Moshe Y. Vardi, Mihalis Yannakakis: Black Box Checking. Journal of Automata, Languages and Combinatorics 7(2): 225-246 (2002)
2001
148EERajeev Alur, Kousha Etessami, Mihalis Yannakakis: Analysis of Recursive State Machines. CAV 2001: 207-220
147EERajeev Alur, Kousha Etessami, Mihalis Yannakakis: Realizability and Verification of MSC Graphs. ICALP 2001: 797-808
146EEChristos H. Papadimitriou, Mihalis Yannakakis: Multiobjective Query Optimization. PODS 2001
145EEMihalis Yannakakis: Approximation of Multiobjective Optimization Problems. WADS 2001: 1
144EERajeev Alur, Mihalis Yannakakis: Model checking of hierarchical state machines. ACM Trans. Program. Lang. Syst. 23(3): 273-303 (2001)
2000
143 Christos H. Papadimitriou, Mihalis Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. FOCS 2000: 86-92
142 Kousha Etessami, Mihalis Yannakakis: From Rule-based to Automata-based Testing. FORTE 2000: 53-68
141EERajeev Alur, Kousha Etessami, Mihalis Yannakakis: Inference of message sequence charts. ICSE 2000: 304-313
140EEMihalis Yannakakis: Hierarchical State Machines. IFIP TCS 2000: 315-330
139EEEdward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis: Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings. SIAM J. Discrete Math. 13(3): 384-402 (2000)
138EEKenneth A. Ross, Charu C. Aggarwal, Alfons Kemper, Sunita Sarawagi, S. Sudarshan, Mihalis Yannakakis: Reminiscences on Influential Papers. SIGMOD Record 29(3): 52-54 (2000)
1999
137EERajeev Alur, Mihalis Yannakakis: Model Checking of Message Sequence Charts. CONCUR 1999: 114-129
136 Doron Peled, Moshe Y. Vardi, Mihalis Yannakakis: Black Box Checking. FORTE 1999: 225-240
135EERajeev Alur, Sampath Kannan, Mihalis Yannakakis: Communicating Hierarchical State Machines. ICALP 1999: 169-178
134EESantosh Vempala, Mihalis Yannakakis: A Convex Relaxation for the Asymmetric TSP. SODA 1999: 975-976
133EEVenkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC 1999: 19-28
132 Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. J. Comput. Syst. Sci. 58(3): 407-427 (1999)
1998
131EEMihalis Yannakakis, David Lee: Testing for Finite State Systems. CSL 1998: 29-44
130 Thomas F. La Porta, David Lee, Yow-Jian Lin, Mihalis Yannakakis: Protocol Feature Interactions. FORTE 1998: 59-74
129EEPierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis: On the complexity of protein folding (abstract). RECOMB 1998: 61-62
128EERajeev Alur, Mihalis Yannakakis: Model Checking of Hierarchical State Machines. SIGSOFT FSE 1998: 175-188
127EEPierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis: On the Complexity of Protein Folding (Extended Abstract). STOC 1998: 597-603
126 Pierluigi Crescenzi, Deborah Goldman, Christos H. Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis: On the Complexity of Protein Folding. Journal of Computational Biology 5(3): 423-466 (1998)
1997
125EEOrna Kupferman, Robert P. Kurshan, Mihalis Yannakakis: Existence of Reduction Hierarchies. CSL 1997: 327-340
124EEChristos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19
123 Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18(1): 3-20 (1997)
122 Mihalis Yannakakis, David Lee: An Efficient Algorithm for Minimizing Real-Time Transition Systems. Formal Methods in System Design 11(2): 113-136 (1997)
121 Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. J. Comput. Syst. Sci. 54(1): 48-60 (1997)
1996
120EEElias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis: Searching a Fixed Graph. ICALP 1996: 280-289
119EEDavid Lee, Mihalis Yannakakis: Optimization problems from feature testing of communication protocols. ICNP 1996: 66-75
118 Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170 (1996)
117 Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput. 25(2): 235-251 (1996)
1995
116 Mihalis Yannakakis: Perspectives on Database Theory. FOCS 1995: 224-246
115EERajeev Alur, Costas Courcoubetis, Mihalis Yannakakis: Distinguishing tests for nondeterministic and probabilistic machines. STOC 1995: 363-372
114 Rajeev Alur, Alon Itai, Robert P. Kurshan, Mihalis Yannakakis: Timing Verification by Successive Approximation Inf. Comput. 118(1): 142-157 (1995)
113EECostas Courcoubetis, Mihalis Yannakakis: The Complexity of Probabilistic Verification. J. ACM 42(4): 857-907 (1995)
112 Mihalis Yannakakis, David Lee: Testing Finite State Machines: Fault Detection. J. Comput. Syst. Sci. 50(2): 209-227 (1995)
111 Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. J. Comput. Syst. Sci. 51(2): 177-196 (1995)
1994
110EEMihalis Yannakakis: Some Open Problems in Approximation. CIAC 1994: 33-39
109EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Multiway Cuts in Directed and Node Weighted Graphs. ICALP 1994: 487-498
108EEChristos H. Papadimitriou, Mihalis Yannakakis: On complexity as bounded rationality (extended abstract). STOC 1994: 726-733
107 David Lee, Mihalis Yannakakis: Testing Finite-State Machines: State Identification and Verification. IEEE Trans. Computers 43(3): 306-320 (1994)
106EEAvrim Blum, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings. J. ACM 41(4): 630-647 (1994)
105EECarsten Lund, Mihalis Yannakakis: On the Hardness of Approximating Minimization Problems. J. ACM 41(5): 960-981 (1994)
104 Mihalis Yannakakis: On the Approximation of Maximum Satisfiability. J. Algorithms 17(3): 475-502 (1994)
103 Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894 (1994)
1993
102EEMihalis Yannakakis, David Lee: An Efficient Algorithm for Minimizing Real-time Transition Systems. CAV 1993: 210-224
101EECarsten Lund, Mihalis Yannakakis: The Approximation of Maximum Subgraph Problems. ICALP 1993: 40-51
100EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover. ICALP 1993: 64-75
99EEMihalis Yannakakis: Recent Developments on the Approximability of Combinatorial Problems. ISAAC 1993: 363-368
98EEChristos H. Papadimitriou, Mihalis Yannakakis: Linear programming without the matrix. STOC 1993: 121-129
97EECarsten Lund, Mihalis Yannakakis: On the hardness of approximating minimization problems. STOC 1993: 286-293
96EENaveen Garg, Vijay V. Vazirani, Mihalis Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications. STOC 1993: 698-707
95 Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). Structure in Complexity Theory Conference 1993: 12-18
94EEChristos H. Papadimitriou, Paolo Serafini, Mihalis Yannakakis: Computing the Throughput of a Network with Dedicated Lines. Discrete Applied Mathematics 42(2): 271-278 (1993)
1992
93EERajeev Alur, Alon Itai, Robert P. Kurshan, Mihalis Yannakakis: Timing Verification by Successive Approximation. CAV 1992: 137-150
92EEVijay V. Vazirani, Mihalis Yannakakis: Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract). ICALP 1992: 366-377
91EEChristos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. PODS 1992: 16-22
90EEMihalis Yannakakis: On the Approximation of Maximum Satisfiability. SODA 1992: 1-9
89 Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract) STOC 1992: 241-251
88 David Lee, Mihalis Yannakakis: Online Minimization of Transition Systems (Extended Abstract) STOC 1992: 264-274
87 Costas Courcoubetis, Moshe Y. Vardi, Pierre Wolper, Mihalis Yannakakis: Memory-Efficient Algorithms for the Verification of Temporal Properties. Formal Methods in System Design 1(2/3): 275-288 (1992)
86 Costas Courcoubetis, Mihalis Yannakakis: Minimum and Maximum Delay Problems in Real-Time Systems. Formal Methods in System Design 1(4): 385-415 (1992)
1991
85 Christos H. Papadimitriou, Mihalis Yannakakis: On the Value of Information in Distributed Decision-Making (Extended Abstract). PODC 1991: 61-64
84EEFoto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25
83 Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis: Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study STOC 1991: 230-240
82 Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis: Linear Approximation of Shortest Superstrings STOC 1991: 328-336
81 Mihalis Yannakakis, David Lee: Testing Finite State Machines (Extended Abstract) STOC 1991: 476-485
80 Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. Ann. Math. Artif. Intell. 3(2-4): 331-360 (1991)
79EEEsther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. J. ACM 38(2): 255-274 (1991)
78 Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3): 425-440 (1991)
77 Mihalis Yannakakis: Expressing Combinatorial Optimization Problems by Linear Programs. J. Comput. Syst. Sci. 43(3): 441-466 (1991)
76 Jeffrey D. Ullman, Mihalis Yannakakis: High-Probability Parallel Transitive-Closure Algorithms. SIAM J. Comput. 20(1): 100-125 (1991)
75 Alejandro A. Schäffer, Mihalis Yannakakis: Simple Local Search Problems That are Hard to Solve. SIAM J. Comput. 20(1): 56-87 (1991)
74 Christos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. Theor. Comput. Sci. 84(1): 127-150 (1991)
1990
73EECostas Courcoubetis, Moshe Y. Vardi, Pierre Wolper, Mihalis Yannakakis: Memory Efficient Algorithms for the Verification of Temporal Properties. CAV 1990: 233-242
72EECostas Courcoubetis, Mihalis Yannakakis: Markov Decision Processes and Regular Events (Extended Abstract). ICALP 1990: 336-349
71EEMihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
70EEJeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53
69EEJeffrey D. Ullman, Mihalis Yannakakis: High-Probability Parallel Transitive Closure Algorithms. SPAA 1990: 200-209
68EEMihalis Yannakakis: The Analysis of Local Search Problems and Their Heuristics. STACS 1990: 298-311
67 Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis: On the Complexity of Local Search (Extended Abstract) STOC 1990: 438-445
66 Christos H. Papadimitriou, Mihalis Yannakakis: On recognizing integer polyhedra. Combinatorica 10(1): 107-109 (1990)
65 Christos H. Papadimitriou, Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19(2): 322-328 (1990)
1989
64EEChristos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. ICALP 1989: 610-620
63EEVijay V. Vazirani, Mihalis Yannakakis: Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs. Discrete Applied Mathematics 25(1-2): 179-190 (1989)
62 Mihalis Yannakakis: Embedding Planar Graphs in Four Pages. J. Comput. Syst. Sci. 38(1): 36-67 (1989)
61 Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. J. Comput. Syst. Sci. 38(2): 360-379 (1989)
1988
60 Costas Courcoubetis, Mihalis Yannakakis: Verifying Temporal Properties of Finite-State Probabilistic Programs FOCS 1988: 338-345
59EEVijay V. Vazirani, Mihalis Yannakakis: Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. ICALP 1988: 667-681
58 Mihalis Yannakakis: Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract) STOC 1988: 223-228
57 Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes (Extended Abstract) STOC 1988: 229-234
56 Christos H. Papadimitriou, Mihalis Yannakakis: Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) STOC 1988: 510-513
55 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988)
54 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy is Local Search? J. Comput. Syst. Sci. 37(1): 79-100 (1988)
1987
53 Mihalis Yannakakis, Fanica Gavril: The Maximum k-Colorable Subgraph Problem for Chordal Graphs. Inf. Process. Lett. 24(2): 133-137 (1987)
52 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Reliable Concurrency Control. SIAM J. Comput. 16(3): 538-553 (1987)
1986
51 Mihalis Yannakakis: Linear and Book Embeddings of Graphs. Aegean Workshop on Computing 1986: 226-235
50EEThanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46
49 Mihalis Yannakakis: Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract) STOC 1986: 104-108
48 Mihalis Yannakakis: Querying Weak Instances. Advances in Computing Research 3: 185-211 (1986)
47 Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs Information and Control 71(3): 181-185 (1986)
46 Ouri Wolfson, Mihalis Yannakakis: Deadlock-Freedom (and Safety) of Transactions in a Distributed Database. J. Comput. Syst. Sci. 33(2): 161-178 (1986)
1985
45 David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy Is Local Search? (Extended Abstract) FOCS 1985: 39-42
44EEOuri Wolfson, Mihalis Yannakakis: Deadlock-Freedom (and Safety) of Transactions in a Distributed Database. PODS 1985: 105-112
43EEChristos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Reliable Concurrency Control. PODS 1985: 230-234
42EEMihalis Yannakakis: A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees J. ACM 32(4): 950-988 (1985)
41 Robert Endre Tarjan, Mihalis Yannakakis: Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 14(1): 254-255 (1985)
1984
40EEMihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280
39 Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis: On Monotone Formulae with Restricted Depth (Preliminary Version) STOC 1984: 480-487
38EEMihalis Yannakakis: Serializability by Locking. J. ACM 31(2): 227-244 (1984)
37 Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141 (1984)
36 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28(2): 244-259 (1984)
35 Robert Endre Tarjan, Mihalis Yannakakis: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579 (1984)
1983
34 Mihalis Yannakakis: A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract) FOCS 1983: 274-281
33EEMihalis Yannakakis, Paris C. Kanellakis, Stavros S. Cosmadakis, Christos H. Papadimitriou: Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract). ICALP 1983: 712-722
32 Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis: On Notions of Information Transfer in VLSI Circuits STOC 1983: 133-139
31EECatriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes J. ACM 30(3): 479-513 (1983)
30 Ronald Fagin, David Maier, Jeffrey D. Ullman, Mihalis Yannakakis: Tools for Template Dependencies. SIAM J. Comput. 12(1): 36-59 (1983)
1982
29EEMarc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
28 Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity) STOC 1982: 255-260
27EEChristos H. Papadimitriou, Mihalis Yannakakis: The complexity of restricted spanning tree problems. J. ACM 29(2): 285-309 (1982)
26EEMihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740 (1982)
25 Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41 (1982)
24 Mihalis Yannakakis: Freedom from Deadlock of Safe Locking Policies. SIAM J. Comput. 11(2): 391-408 (1982)
1981
23 Christos H. Papadimitriou, Mihalis Yannakakis: Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract) FOCS 1981: 358-363
22 Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes STOC 1981: 355-362
21 Mihalis Yannakakis: Issues of Correctness in Database Concurrency Control by Locking STOC 1981: 363-367
20EEMihalis Yannakakis: Algorithms for Acyclic Database Schemes VLDB 1981: 82-94
19 Christos H. Papadimitriou, Mihalis Yannakakis: On Minimal Eulerian Graphs. Inf. Process. Lett. 12(4): 203-205 (1981)
18 Christos H. Papadimitriou, Mihalis Yannakakis: The Clique Problem for Planar Graphs. Inf. Process. Lett. 13(4/5): 131-133 (1981)
17 Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Testing Whether a Graph is a Superconcentrator. Inf. Process. Lett. 13(4/5): 164-167 (1981)
16EEDavid Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695 (1981)
15 Mihalis Yannakakis: Edge-Deletion Problems. SIAM J. Comput. 10(2): 297-309 (1981)
14 Mihalis Yannakakis: Node-Deletion Problems on Bipartite Graphs. SIAM J. Comput. 10(2): 310-327 (1981)
1980
13 Mihalis Yannakakis: On a Class of Totally Unimodular Matrices FOCS 1980: 10-16
12 Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract) FOCS 1980: 328-332
11 Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19 (1980)
10EEYehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655 (1980)
9 John M. Lewis, Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230 (1980)
1979
8 Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis: Modeling Communications Protocols by Automata FOCS 1979: 267-273
7 Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock FOCS 1979: 286-297
6EEChristos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract). ICALP 1979: 460-470
5 Mihalis Yannakakis, Theodosios Pavlidis: Topological Characterization of Families of Graphs Generated by Certain Types of Graph Grammars Information and Control 42(1): 72-86 (1979)
4EEMihalis Yannakakis: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems. J. ACM 26(4): 618-630 (1979)
3 Christos H. Papadimitriou, Mihalis Yannakakis: Scheduling Interval-Ordered Tasks. SIAM J. Comput. 8(3): 405-409 (1979)
1978
2 Mihalis Yannakakis: Node- and Edge-Deletion NP-Complete Problems STOC 1978: 253-264
1EEYehoshua Sagiv, Mihalis Yannakakis: Equivalence among Relational Expressions with the Union and Difference Operation. VLDB 1978: 535-548

Coauthor Index

1Foto N. Afrati [84] [111]
2Charu C. Aggarwal [138]
3Alfred V. Aho [8] [32]
4Rajeev Alur [93] [114] [115] [128] [135] [137] [141] [144] [147] [148] [155] [156] [164] [165]
5Esther M. Arkin [79]
6Catriel Beeri [22] [31]
7Michael Benedikt [165]
8Avrim Blum [82] [106]
9Manuel Blum [17]
10Swarat Chaudhuri [156]
11Edward G. Coffman Jr. [83] [139]
12Stavros S. Cosmadakis [33] [84] [111]
13Costas Courcoubetis [60] [72] [73] [83] [86] [87] [113] [115] [139]
14Pierluigi Crescenzi (Pilu Crescenzi) [126] [127] [129]
15Elias Dahlhaus [89] [103]
16Ilias Diakonikolas [181] [186] [189]
17Kousha Etessami [141] [142] [147] [148] [155] [156] [164] [165] [166] [167] [169] [170] [171] [174] [177] [179] [180] [182] [183] [184] [185] [190] [191] [193]
18Ronald Fagin [22] [30] [31]
19M. R. Garey (Michael R. Garey) [83] [139]
20Naveen Garg [96] [100] [109] [117] [123] [158]
21Fanica Gavril [53]
22Patrice Godefroid [165]
23Deborah Goldman [126] [127] [129]
24Marc H. Graham [29] [37]
25Alex Groce [151] [153] [172]
26Sudipto Guha [156]
27Venkatesan Guruswami [133] [154]
28Thanasis Hadzilacos [50] [61]
29Peter Honeyman [11]
30Alon Itai [93] [114]
31Tao Jiang [82]
32David S. Johnson [45] [54] [55] [83] [89] [103] [139]
33Paris C. Kanellakis [33]
34Sampath Kannan [135] [157]
35Richard M. Karp [17]
36Alfons Kemper [138]
37Sanjeev Khanna [133] [154]
38Maria M. Klawe [39]
39Elias Koutsoupias [120]
40H. T. Kung [7]
41Orna Kupferman [125]
42Robert P. Kurshan [93] [114] [125]
43Marta Z. Kwiatkowska [179] [183] [184]
44Richard E. Ladner [11]
45David Lee [81] [88] [102] [107] [112] [119] [122] [130] [131] [150] [159] [175]
46John M. Lewis [9]
47Ming Li [82] [106]
48Yow-Jian Lin [130]
49Christine Liu [159]
50Carsten Lund [97] [101] [105]
51David Maier [16] [22] [30] [31]
52Lyle A. McGeoch [83]
53Alberto O. Mendelzon [22]
54Damon Mosk-Aoyama [168]
55Christos H. Papadimitriou [3] [6] [7] [12] [17] [18] [19] [23] [25] [27] [28] [33] [36] [43] [45] [47] [52] [54] [55] [56] [57] [64] [65] [66] [67] [74] [78] [79] [85] [89] [91] [94] [95] [98] [103] [108] [118] [120] [121] [124] [126] [127] [129] [132] [143] [146]
56Wolfgang J. Paul [39]
57Theodosios Pavlidis (Theo Pavlidis) [5]
58Doron Peled [136] [149] [151] [153] [172]
59Antonio Piccolboni [126] [127] [129]
60Nicholas Pippenger [39]
61Thomas F. La Porta (Tom La Porta) [130]
62Rajmohan Rajaraman [133] [154]
63Thomas W. Reps [165]
64Kenneth A. Ross [138]
65Yehoshua Sagiv [1] [10] [16]
66Sunita Sarawagi [138]
67Alejandro A. Schäffer [67] [75]
68Paolo Serafini [94]
69Paul D. Seymour [89] [103]
70F. Bruce Shepherd [133] [154]
71Peter W. Shor [83] [139]
72Guoqiang Shu [175]
73S. Sudarshan [138]
74Robert Endre Tarjan [35] [41]
75John Tromp [82] [106]
76Jeffrey D. Ullman [8] [22] [30] [32] [69] [70] [76] [80]
77Moshe Y. Vardi [73] [87] [136] [149] [179] [183] [184]
78Sergei Vassilvitskii [162] [163]
79Vijay V. Vazirani [59] [63] [92] [96] [100] [109] [117] [123] [158]
80Santosh Vempala [134]
81Oliver Vornberger [17]
82Richard R. Weber [83] [139]
83Dominik Wojtczak [190] [191]
84Ouri Wolfson [44] [46]
85Pierre Wolper [73] [87]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)