bibliography mihalis



  1. M. Yannakakis, Node and Edge-Deletion NP -Complete Problems, 10th Annual ACM Symposium on Theory of Computing, 1978.
  2. M. Yannakakis and T. Pavlidis, Topological Characterizations of Families of Graphs Generated by Certain Types of Graph-Grammars, 1978 Conf. on Image Processing and Pattern Recognition, 1978, (Full version in it Information and Control bf 42 (1) pp. 72-86 July 1979.) .
  3. Y. Sagiv and M. Yannakakis, Equivalence Among Relational Expressions with the Union and Difference Operations, 4th Intl. Conf. on Very Large Data Bases, 1978, (Full version in it J. Assoc. Comput. Mach. October 1980) .
  4. C. H. Papadimitriou and M. Yannakakis, The Complexity of Restricted Spanning Tree Problems, 6th Int. Coll. on Automata Languages and Programming, 1979, (Full version in it J. ACM 29 (2) pp. 285-309 1982.) .
  5. C. H. Papadimitriou and M. Yannakakis, Scheduling Interval Ordered Tasks, SIAM J. Computing, Vol. 8, 3, pp. 405--409, 1979.
  6. M. Yannakakis, The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems, J. Assoc. Comp. Mach., Vol. 26, 4, 1979.
  7. M. Yannakakis and C. H. Papadimitriou and H. T. Kung, Locking Policies: Safety and Freedom from Deadlock, Proc. 20th Ann. IEEE Symp. on Foundations of Computing Science, pp. 286--297, 1979.
  8. A. V. Aho and J. D. Ullman and M. Yannakakis, Modeling Communication Protocols by Automata, Proc. 20th Ann. IEEE Symp. on Foundations of Computer Science, pp. 267--273, 1979.
  9. P. Honeyman and R. E. Ladner and M. Yannakakis, Testing the Universal Instance Assumption, Information Processing Letters, Vol. 10, 1, pp. 14--19, 1980.
  10. A. V. Aho and T. G. Szymanski and M. Yannakakis, Sorting the Cartesian Product, Proc. Princeton Conf. on Inf. Science and Systems, pp. 557--558, 1980.
  11. J. M. Lewis and M. Yannakakis, The Node-deletion Problem for Hereditary Properties is NP -complete, J. Comp. Sys. Sci., Vol. 20, 2, pp. 219--230, 1980, ((special issue for 10th STOC)) .
  12. M. Yannakakis and F. Gavril, Edge Dominating Sets in Graphs, SIAM J. Appl. Math, Vol. 38, 3, pp. 364--372, 1980.
  13. M. Yannakakis and C. H. Papadimitriou, Algebraic Dependencies, Proc. 21st IEEE Symp. on Foundations of Computer Science, pp. 328--332, Syracuse New York, 1980, (Full version in it J. Computer System Sci. 25 (1) (special isssue for 21st FOCS) pp. 2-41 1982.) .
  14. M. Yannakakis, On a Class of Totally Unimodular Matrices, Proc. 21st IEEE Symp. on Foundations of Computer Science, pp. 10--16, Syracuse New York, 1980, (Full version in it Mathematics of Operations Research bf 10 (2) pp.280-304 1985.) .
  15. M. Yannakakis, The Complexity of the Partial Order Dimension Problem, SIAM J. on Alg. Disc. Meth., Vol. 3, 3, pp. 351--358, 1982.
  16. C. Beeri and R. Fagin and D. Maier and M. Yannakakis, On the Desirability of Acyclic Database Schemes, JACM, Vol. 30, 3, pp. 479--513, 1983.
  17. C. Beeri and R. Fagin and D. Maier and A. Mendelzon and J. D. Ullman and M. Yannakakis, Properties of Acyclic Database Schemes, 13th Annual ACM Symp. on theory of Computing, 1981.
  18. R. Fagin and D. Maier and J. D. Ullman and M. Yannakakis, Tools for Template Dependencies, SIAM J. on Computing, Vol. 12, 1, pp. 36--59, 1983.
  19. C. H. Papadimitriou and M. Yannakakis, The Clique Problem for Planar Graphs, Information Processing Letters, Vol. 13, 4, pp. 131--133, 1981.
  20. M. Blum and R. Karp and C. H. Papadimitriou and O. Vornberger and M. Yannakakis, The Complexity of Testing Whether a Graph is a Superconcentrator, Information Processing Letters, Vol. 13, 4, pp. 164--167, 1981.
  21. M. Yannakakis, Computing The Minimum Fill-In is NP -Complete, SIAM J. on Algebraic and Discrete Methods, pp. 77--79, 1981.
  22. M. Yannakakis, Edge-deletion Problems, SIAM J. Computing, pp. 297--309, 1981.
  23. M. Yannakakis, Issues of Correctness in Database Concurrency Control by Locking, 13th Annual ACM Symp. on Theory of Computing, pp. 363--367, 1981.
  24. M. Yannakakis, Node-Deletion Problems on Bipartite Graphs, SIAM J. Computing, pp. 310--327, 1981.
  25. C. H. Papadimitriou and M. Yannakakis, On Minimal Eulerian Graphs, Information Processing Letters, Vol. 12, 4, pp. 203--205, 1981.
  26. M. Yannakakis, Algorithms for Acyclic Database Schemes, 7th Int l. Conf. on Very Large Data Bases, 1981.
  27. D. Maier and Y. Sagiv and M. Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, J. Assoc. Comp. Mach., pp. 680--695, 1981.
  28. C. H. Papadimitriou and M. Yannakakis, Worst-case Ratios in Planar Graphs and the Method of Induction on Faces, 22nd Annual IEEE Symp. on Foundations of Comp. Sci., 1981.
  29. A. V. Aho and J. D. Ullman and A. Wyner and M. Yannakakis, Bounds on the Size and Transmission Rate of Communication Protocols, Computers and Math with Applications, Vol. 8, 3, pp. 205--214, 1982.
  30. M. Graham and M. Yannakakis, Independent Database Schemes, Proc. 1st SIGACT-SIGMOD Conf. on Principles of Database Systems, 1982, (Full version in it J. Computer System Sci. 28(1) (special isssue for 1st PODS) pp. 121-141 1984.) .
  31. C. H. Papadimitriou and M. Yannakakis, The Complexity of Facets (and some Facets of Complexity), Proc. 14th Annual ACM Symp. on Theory of Computing, 1982, (Full version in it J. Computer System Sci. 28 (2) (special issue for 14th STOC) pp. 244-259 1984.) .
  32. M. Yannakakis, Freedom from Deadlock of Safe Locking Policies, SIAM Journal on Computing, pp. 391--408, 1982.
  33. M. Yannakakis, A Theory of Safe Locking Policies in Database Systems, J. Assoc. Comp. Mach., pp. 718--740, 1982.
  34. M. R. Garey D. S. Johnson R. E. Tarjan and M. Yannakakis, Scheduling Opposing Forests, SIAM Journal on Alg. Disc. Meth., Vol. 4, 1, pp. 72--93, 1983.
  35. R. E. Tarjan and M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs Test Acyclicity of Hypergraphs and Selectively Reduce Acyclic Hypergraphs, SIAM J. on Computing, Vol. 13, 3, pp. 566--579, 1984, (Addendum: bf 14 (1) pp.254-255 1985.) .
  36. E. G. Coffman and M. Yannakakis, Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum, Mathematics of Operations Research, Vol. 9, 3, pp. 384--390, 1984.
  37. M. Yannakakis, Serializability by Locking, JACM, Vol. 31, 2, pp. 227--244, 1984.
  38. A. V. Aho and J. D. Ullman and M. Yannakakis, On Notions of Information Transfer in VLSI Circuits, Proc. 15th Annual ACM Symp. on Theory of Computing, pp. 133--139, 1983.
  39. M. Yannakakis and P. C. Kanellakis and S. C. Cosmadakis and C. H. Papadimitriou, Cutting and Partitioning a Graph After a Fixed Pattern, Proc. 10th Int. Coll. on Automata Languages and Programming, pp. 712--722, 1983.
  40. M. Yannakakis, A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees, Proc. 24th Annual Symp. on Foundations of Computer Science, pp. 274--281, 1983, (Full version in it JACM bf 32 (4) pp. 950-988 1985.) .
  41. M. Yannakakis, Querying Weak Instances, Proc. 3rd SIGACT-SIGMOD Symp. on Principles of Database Systems, pp. 275--280, 1984, (Full version in it The Theory of Databases Advances in Computing Research bf 3 1985.) .
  42. M. Klawe and W. Paul and N. Pippenger and M. Yannakakis, On Monotone Formulae with Restricted Depth, Proc. 16th Annual ACM Symp. on Theory of Computing, pp. 480--487, 1984.
  43. O. Wolfson and M. Yannakakis, Deadlock-Freedom (and Safety) of Transactions in a Distributed Database, Proc. 4th SIGACT-SIGMOD Symp. on Principles of Database Systems, pp. 105--112, 1985, (Full version in it J. of Computer and System Sci. 33 (2) (special issue for 4th PODS) pp. 161-178 1986.) .
  44. C. Papadimitriou and M. Yannakakis, The Complexity of Reliable Concurrency Control, Proc. 4th SIGACT-SIGMOD Symp. on Principles of Database Systems, pp. 230--234, 1985, (Also it SIAM Journal on Computing bf 16 (3) pp. 538-553 1987.) .
  45. D. S. Johnson and C. H. Papadimitriou and M. Yannakakis, How Easy is Local Search?, Proc. 26th Annual Symp. on Foundations of Computer Science, pp. 39--42, 1985, (Also it J. Computer System Sci. bf 37 (1) pp. 79-100 1988.) .
  46. T. Hadzilacos and M. Yannakakis, Deleting Completed Transactions, Proc. 5-th SIGACT-SIGMOD Symp. on Principles of Database Systems, pp. 43--46, 1986, (Also it J. Computer System Sci. bf 38 (2) (special issue for 5th PODS) pp. 360-379 1989.) .
  47. M. Yannakakis, Four Pages are Necessary and Sufficient for Planar Graphs, Proc. 18-th Annual ACM Symp. on Theory of Computing, pp. 104--108, 1986.
  48. M. Yannakakis, Linear and Book Embeddings of Graphs, Proc. Aegean Workshop on Computing Springer-Verlag LNCS 227, pp. 226--235, 1986, (invited paper) .
  49. C. H. Papadimitriou and M. Yannakakis, A Note on Succinct Representations of Graphs, Information and Control 71(3), pp. 181--185, 1987.
  50. M. Yannakakis and F. Gavril, The Maximum k-Colorable Subgraph Problem for Chordal Graphs, Information Processing Letters 24, pp. 133--137, 1987.
  51. M. Yannakakis, Embedding Planar Graphs in Four Pages, J. Computer and System Sci., Vol. 38, 1, pp. 36--67, 1989, (special issue for 18th STOC) .
  52. D. S. Johnson and C. H. Papadimitriou and M. Yannakakis, On Generating All Maximal Independent Sets, Information Processing Letters, Vol. 27, 3, pp. 119--123, 1988.
  53. C. H. Papadimitriou and M. Yannakakis, Towards An Architecture-Independent Analysis of Parallel Algorithms, Proceedings of 20th Annual ACM Symposium on Theory of Computing, pp. 510--513, 1988, (Full version in it SIAM J. on Computing bf 19 (2) pp. 322-328 1990.) .
  54. C. H. Papadimitriou and M. Yannakakis, Optimization Approximation and Complexity Classes, Proceedings of 20th Annual ACM Symposium on Theory of Computing, pp. 229--234, 1988, (Full version in it J. of Computer and System Sci. 43(3) (special issue for 20th STOC) pp. 425-440 1991.) .
  55. M. Yannakakis, Expressing Combinatorial Optimization Problems by Linear Programs, Proceedings of 20th Annual ACM Symposium on Theory of Computing, pp. 223--228, 1988, (Full version in it J. of Computer and System Sci. 43(3) (special issue for 20th STOC) pp. 441-466 1991.) .
  56. V. V. Vazirani and M. Yannakakis, Pfaffian Orientations 0 1 Permanents and Even Cycles in Directed Graphs, Proc. 15th Intl. Coll. Automata Languages and Programming, pp. 667--681, 1988, (Full version in it Disc. Appl. Math. bf 25 (1-2) pp. 179-190 1989.) .
  57. C. Courcoubetis and M. Yannakakis, Verifying Temporal Properties of Finite-State Probabilistic Programs, Proc. 29th Annual Symp. on Foundations of Computer Science, pp. 338--345, 1988.
  58. C. Papadimitriou and M. Yannakakis, On Recognizing Integer Polyhedra, Combinatorica, Vol. 10, 1, pp. 107--109, 1990.
  59. C. Papadimitriou and M. Yannakakis, Shortest Paths Without a Map, Proc. 16th Intl. Coll. Automata Languages and Programming, pp. 610--620, 1989, (Full version in it Theoretical Computer Science 84(1) (special issue for 16th ICALP) pp. 127-150 1991.) .
  60. E. G. Coffman Jr. and A. Nozari and M. Yannakakis, Optimal Scheduling of Products With Two Subassemblies on a Single Machine, Operations Research, Vol. 37, 3, pp. 426--436, 1989.
  61. M. Yannakakis, The Analysis of Local Search Problems and Their Heuristics, Proc. 7th Annual Symp. on Theoretical Aspects of Computer Science, pp. 298--311, 1990, (invited paper. Also Chech translation in it Pokroky Matematiky Fyziky a Astronomie 37(1) pp. 12-30 1992) .
  62. M. Yannakakis, Graph Theoretic Methods in Database Theory, Proc. 9th ACM Symp. on Principles of Database Systems, pp. 230--242, 1990, (invited paper) .
  63. C. H. Papadimitriou and A. Schaffer and M. Yannakakis, On the Complexity of Local Search, Proc. 22nd Annual ACM Symp. on Theory of Computing, pp. 438--445, 1990.
  64. J. D. Ullman and M. Yannakakis, The Input Output Complexity of Transitive Closure, Proc. 1990 ACM SIGMOD Intl. Conf. on Management of Data, pp. 44--53, 1990, (Full version in it Annals of Mathematics and Artificial Intelligence 3 pp. 331-360 1991) .
  65. C. Courcoubetis and M. Yannakakis, Markov Decision Processes and Regular Events, Proc. 17th Intl. Coll. on Automata Languages and Programming, pp. 336--349, 1990, (Full version in it IEEE Trans. on Automatic Control 43(10) pp. 1399-1418 1998) .
  66. J. D. Ullman and M. Yannakakis, High Probability Parallel Transitive Closure Algorithms, Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, pp. 200--209, 1990, (Full version in it SIAM J. on Computing 20 (1) pp. 100-125 1991) .
  67. E. M. Arkin and C. H. Papadimitriou and M. Yannakakis, Modularity of Cycles and Paths in Graphs, J. Assoc. Comp. Mach., Vol. 38, 2, pp. 255--274, 1991.
  68. A. Schaffer and M. Yannakakis, Simple Local Search Problems That Are Hard to Solve, SIAM J. on Computing, Vol. 20, 1, pp. 56--87, 1991.
  69. C. Courcoubetis and M. Vardi and P. Wolper and M. Yannakakis, Memory Efficient Algorithms for the Verification of Temporal Properties, Proc. 2nd Workshop on Computer-Aided Verification, pp. 207--218, 1990, (Full version in it Formal Methods in System Design (special issue for 2nd CAV) 1 pp. 275-288 1992) .
  70. E. G. Coffman Jr and M. J. Magazine and C. Santos and M. Yannakakis, Batch Sizing and Job Sequencing on a Single Machine, Annals of Operations Research, Vol. 26, pp. 135--147, 1990.
  71. C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem With Distances One and Two, Mathematics of Operations Research, Vol. 18, pp. 1--11, 1993.
  72. E. G. Coffman Jr. and C. A. Courcoubetis and M. R. Garey and D. S. Johnson and L. A. McGeoch and P. W. Shor and R. R. Weber and M. Yannakakis, Fundamental Discrepancies Between Average Case Analyses Under Discrete and Continuous Distributions: A Bin Packing Case Study, Proc. 23rd Annual ACM Symp. on Theory of Computing, pp. 230--240, 1991.
  73. A. Blum and T. Jiang and M. Li and J. Tromp and M. Yannakakis, Linear Approximation of Shortest Superstrings, Proc. 23rd Annual ACM Symp. on Theory of Computing, pp. 328--336, 1991, (Also it J. Assoc. Comp. Mach. 41(4) pp. 630-647 1994) .
  74. M. Yannakakis and D. Lee, Testing Finite State Machines, Proc. 23rd Annual ACM Symp. on Theory of Computing, pp. 476--485, 1991.
  75. F. Afrati and S. Cosmadakis and M. Yannakakis, On Datalog vs. Polynomial Time, Proc. 10th Annual ACM Symp. on Principles of Database Systems, pp. 13--25, 1991, (Full version in it J. Computer and System Sci. (special issue for 10th PODS) 51(2) pp. 177-196 1995) .
  76. C. H. Papadimitriou and M. Yannakakis, On the Value of Information in Distributed Decision-Making, Proc. 10th Annual ACM Symp. on Principles of Distributed Computing, pp. 61--64, 1991.
  77. C. Courcoubetis and M. Yannakakis, Minimum and Maximum Delay Problems in Real Time Systems, Proc. 3rd Workshop on Computer-Aided Verification, 1991, (Full version in it Formal Methods in System Design (special issue for 3rd CAV) 1(4) pp. 385-415 1992) .
  78. M. Yannakakis, On the Approximation of Maximum Satisfiability, Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 1--9, 1992, (Full version in it J. Algorithms (special issue for 3rd SODA) pp. 475-502 1994) .
  79. E. Dalhaus and D. S. Johnson and C. H. Papadimitriou and P. D. Seymour and M. Yannakakis, The Complexity of Multiway Cuts, Proc. 24th Annual ACM Symp. on Theory of Computing, pp. 241--251, 1992.
  80. D. Lee and M. Yannakakis, Online Minimization of Transition Systems, Proc. 24th Annual ACM Symp. on Theory of Computing, pp. 264--274, 1992.
  81. V. V. Vazirani and M. Yannakakis, Suboptimal Cuts: Their Enumeration Weight and Number, Proc. 19th Intl. Coll. on Automata Languages and Programming, pp. 366--377, 1992.
  82. C. H. Papadimitriou and M. Yannakakis, Tie-Breaking Semantics and Structural Totality, Proc. 11th ACM Symp. on Principles of Database Systems, pp. 16--22, 1992, (Full version in it J. Computer and System Sciences (special issue for 11th PODS) 54 (1) pp. 48-60 1997) .
  83. R. Alur A. Itai R. Kurshan and M. Yannakakis, Timing Verification by Successive Approximation, Proc. 4th Workshop on Computer-Aided Verification, 1992, (Full version in it Information and Computation 118(1). pp. 142-157 1995.) .
  84. D. Lee and M. Yannakakis, Testing Finite State Machines: Fault Detection, J. of Computer and System Sciences, Vol. 50, pp. 209--227, 1995, (special issue for 23rd STOC) .
  85. D. Lee and M. Yannakakis, Testing Finite State Machines: State Identification and Verification, IEEE Trans. on Computers, Vol. 43, pp. 306--320, 1994.
  86. C. H. Papadimitriou and P. Serafini and M. Yannakakis, Computing the Throughput of a Network with Dedicated Lines, Discrete Applied Mathematics, Vol. 42, pp. 271--278, 1993.
  87. C. H. Papadimitriou and M. Yannakakis, On Limited Nondeterminism and the Complexity of the V - C Dimension, Proc. 8th Annual IEEE Conf. on Structure in Complexity Theory, pp. 12--18, 1993, (Full version in it J. Computer and System Sciences (special issue for 8th Structures) 53(2) pp. 161-170 1996) .
  88. C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems, Proc. 25th Annual ACM Symp. on Theory of Computing, pp. 286--293, 1993, (Full version in it J. ACM 41(5) pp. 960-981 1994.) .
  89. N. Garg and V. V. Vazirani and M. Yannakakis, Approximate Max-Flow Min-(Multi)cut Theorems and Their Applications, Proc. 25th Annual ACM Symp. on Theory of Computing, pp. 698--707, 1993, (Full version in it SIAM J. of Computing 25(2) pp. 235-251 1996) .
  90. C. H. Papadimitriou and M. Yannakakis, Linear Programming without the Matrix, Proc. 25th Annual ACM Symp. on Theory of Computing, pp. 121--129, 1993.
  91. C. Lund and M. Yannakakis, The Approximation of Maximum Subgraph Problems, Proc. 20th Intl. Coll. on Automata Languages and Programming, pp. 40--51, 1993.
  92. N. Garg and V. V. Vazirani and M. Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees with Applications to Matching and Set Cover, Proc. 20th Intl. Coll. on Automata Languages and Programming, pp. 64--75, 1993, (Full version in it Algorithmica 18 pp. 3-20 1997.) .
  93. M. Yannakakis and D. Lee, An Efficient Algorithm for Minimizing Real-Time Transition Systems, Proc. 5th Conference on Computer-Aided Verification, pp. 210--224, 1993, (Full version in it Formal Methods in System Design (special issue for 5th CAV) 11 pp. 113-136 1997.) .
  94. E. Dalhaus and D. S. Johnson and C. H. Papadimitriou and P. D. Seymour and M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM J. of Computing, Vol. 23, pp. 864--894, 1994.
  95. M. Yannakakis, Recent Developments in the Approximability of Combinatorial Problems, Proc. 4th Intl. Symposium on Algorithms and Computation, pp. 363--368, 1993, (invited paper) .
  96. M. Yannakakis, Some Open Problems in Approximation, Proc. 2nd Italian Conf. on Algorithms and Complexity, pp. 33--39, 1994, (invited paper) .
  97. C. H. Papadimitriou and M. Yannakakis, On Complexity as Bounded Rationality, Proc. 26th Annual ACM Symp. on Theory of Computing, pp. 726--733, 1994.
  98. N. Garg and V. V. Vazirani and M. Yannakakis, Multiway Cuts in Directed and Node Weighted Graphs, Proc. 21st Intl. Coll. on Automata Languages and Programming, pp. 487--498, 1994.
  99. C. Courcoubetis and M. Yannakakis, The Complexity of Probabilistic Verification, Journal of ACM, Vol. 42, pp. 857--907, 1995.
  100. D. Lee and M. Yannakakis, Principles and Methods of Testing Finite State Machines - A Survey, Proceedings of the IEEE, Vol. 84, pp. 1090--1126, 1996.
  101. M. Yannakakis, Computational Complexity of Local Search, Local Search in Combinatorial Optimization, 1997, (E.H.L. Aarts J.K. Lenstra eds. John Wiley) .
  102. R. Alur and C. Courcoubetis and M. Yannakakis, Distinguishing Tests for Nondeterministic and Probabilistic Machines, Proc. 27th Annual ACM Symp. on Theory of Computing, pp. 363--372, 1995.
  103. M. Yannakakis, Perspectives on Database Theory, Proc. 36th Annual Symp. on Foundations of Computer Science, pp. 224--246, 1995, (invited) .
  104. E. Koutsoupias and C. H. Papadimitriou and M. Yannakakis, Searching a Fixed Graph, Proc. 23rd Intl. Coll. on Automata Languages and Programming, 1996.
  105. G.J. Holzmann and D. Peled and M. Yannakakis, On Nested Depth First Search, Proc. Second SPIN Workshop, pp. 23-32, American Mathematical Society, 1996.
  106. D. Lee and M. Yannakakis, Optimization Problems from Feature Testing of Communication Protocols, Proc. Intl. Conf. on Network Protocols, pp. 66--75, 1996.
  107. D. Lee and M. Yannakakis, Conformance Testing, Encyclopedia of Electrical and Electronics Engineering, 1998, (J. Webster ed. John Wiley) .
  108. P.Crescenzi and D. Goldman and C. Papadimitriou and A. Piccolboni and M. Yannakakis, On the Complexity of Protein Folding, Proc. 30th Annual ACM Symp. on Theory of Computing, pp. 597-603, 1998, (Abstract also in it Proc. RECOMB 98. Full version in it J. Comp. Biology 5(3) pp. 423-466 1999) .
  109. C. H. Papadimitriou and M. Yannakakis, On the Complexity of Database Queries, Proc. 16th Annual ACM Symp. on Principles of Database Systems, 1997, (Full version in it J. Comp. and Syst. Sc. (special issue for 16th PODS) 58(3) pp. 407-427 1999) .
  110. O. Kupferman and R. Kurshan and M. Yannakakis, Existence of Reduction Hierarchies, Proc. 1997 Annual Conf. of the Eur. Assoc. for Comp. Sci. Logic, pp. 327-340, Springer Verlag, 1997.
  111. R. Alur and M. Yannakakis, Model Checking of Hierarchical State Machines, Proc. 6th ACM Symp. on Foundations of Software Engineering, pp. 175-188, 1998, (Full version in ACM Trans. on Programming Languages and Systems to appear) .
  112. T. F. LaPorta and D. Lee and Y.-J. Lin and M. Yannakakis, Protocol Feature Interactions, Proc. FORTE-PSTV, 1998.
  113. M. Yannakakis and D. Lee, Testing of Finite State Systems, Proc. 1998 Annual Conf. of the Eur. Assoc. for Comp. Sci. Logic, pp. 29-44, Springer Verlag, 1998, (invited) .
  114. S. Vempala and M. Yannakakis, A Convex Relaxation for the Asymmetric TSP, Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms, 1999.
  115. R. Alur and M. Yannakakis, Model Checking of Message Sequence Charts, Proc. 10th Intl. Conf. on Concurrency Theory, pp. 114-129, Springer Verlag, 1999.
  116. R. Alur and S. Kannan and M. Yannakakis, Communicating Hierarchical State Machines, Proc. 26th Intl. Coll. on Automata Languages and Programming, Springer Verlag, 1999.
  117. V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis, Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems, Proc. 31st ACM Symp. on Theory of Computing, pp. 19-28, 1999.
  118. M. Yannakakis, Complexity of Local Search, 3rd Metaheuristics Intl. Conf., 1999, (invited) .
  119. D. Peled and M. Vardi and M. Yannakakis, Black Box Checking, Proc. FORTE PSTV, pp. 225-240, Kluwer, 1999.
  120. E. G. Coffman Jr. and C. A. Courcoubetis and M. R. Garey and D. S. Johnson and P. W. Shor and R. R. Weber and M. Yannakakis, Bin Packing with Discrete Intem Sizes Part I: Perfect packing Theorems and the Average Case Behavior of Optimal Packings, SIAM J. on Discrete Math., Vol. 13, 3, pp. 384-402, 2000.
  121. C. H. Papadimitriou and M. Yannakakis, On the Approximability of Trade-Offs and Optimal Access of Web Sources, Proc. 41st Annual IEEE Symp. on Foundations of Computer Science, pp. 86-92, 2000.
  122. R. Alur and K Etessami and M. Yannakakis, Inference of Message Sequence Charts, Proc. 22nd Intl. Conf. on Software Engineering, pp. 304-313, 2000.
  123. K Etessami and M. Yannakakis, From Rule-Based to Automata-Based Testing, Proc. FORTE-PSTV: 20th IFIP Int. Conf. on Formal Description Techniques Protocol Specification Testing and Verification, 2000.
  124. M. Yannakakis, Hierarchical State Machines, Proc. 1st IFIP Conf. on Theoretical Computer Science, Vol. LNCS 1872, pp. 315-330, Springer-Verlag, 2000, (invited paper) .
  125. C. H. Papadimitriou and M. Yannakakis, Multiobjective Query Optimization, Proc. 20th ACM Symp. on Principles of Database Systems, 2001.
  126. R. Alur and K. Etessami and M. Yannakakis, Analysis of Recursive State Machines, Proc. 13th Conf. on Computer-Aided Verification, 2001.
  127. R. Alur and K. Etessami and M. Yannakakis, Realizability and Verification of MSC graphs, Proc. 28th Int. Col. on Automata Languages and Programming, 2001.

Go to the Computing Sciences Research Center home page.
Modified: December, 1997.
Copyright © 1997 Lucent Technologies. All rights reserved.