Mihalis Yannakakis

According to our database1, Mihalis Yannakakis authored at least 257 papers between 1978 and 2019.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 1998, "For seminal contributions to the foundations of computer science, the principles of database systems, and the links between complexity theory and combinatorial optimization.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
REACT to Cyber Attacks on Power Grids.
IEEE Trans. Network Science and Engineering, 2019

Recursive stochastic games with positive rewards.
Theor. Comput. Sci., 2019

The Complexity of Finding {$S$}-factors in Regular Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.
CoRR, 2019

Alembic: Automated Model Inference for Stateful Network Functions.
Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation, 2019

Fixed Point Computation Problems and Facets of Complexity (Invited Talk).
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Reachability for Branching Concurrent Stochastic Games.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Power Grid State Estimation Following a Joint Cyber and Physical Attack.
IEEE Trans. Control of Network Systems, 2018

REACT to Cyber-Physical Attacks on Power grids (Extended Abstract).
SIGMETRICS Performance Evaluation Review, 2018

Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes.
Inf. Comput., 2018

The complexity of optimal multidimensional pricing for a unit-demand buyer.
Games and Economic Behavior, 2018

Reachability for Branching Concurrent Stochastic Games.
CoRR, 2018

Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis.
CoRR, 2018

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis.
Proceedings of the Robotics: Science and Systems XIV, 2018

2017
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes.
SIAM J. Comput., 2017

The Complexity of Non-Monotone Markets.
J. ACM, 2017

REACT to Cyber Attacks on Power Grids.
CoRR, 2017

On the Complexity of Bundle-Pricing and Simple Mechanisms.
CoRR, 2017

Doubly Balanced Connected Graph Partitioning.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016
How Good is the Chord Algorithm?
SIAM J. Comput., 2016

Doubly Balanced Connected Graph Partitioning.
CoRR, 2016

2015
Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata.
J. ACM, 2015

Recursive Markov Decision Processes and Recursive Stochastic Games.
J. ACM, 2015

Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes.
CoRR, 2015

Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery.
Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2015

Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing.
TOCT, 2014

The Complexity of Optimal Multidimensional Pricing.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing.
Electronic Colloquium on Computational Complexity (ECCC), 2013

A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
CoRR, 2013

Stochastic Context-Free Grammars, Regular Languages, and Newton's Method
CoRR, 2013

Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
CoRR, 2013

How good is the Chord algorithm?
CoRR, 2013

The Complexity of Optimal Multidimensional Pricing.
CoRR, 2013

Analysis of Boolean Programs.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2013

The complexity of non-monotone markets.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Stochastic Context-Free Grammars, Regular Languages, and Newton's Method.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata.
Proceedings of the Computer Aided Verification - 25th International Conference, 2013

2012
Model Checking of Recursive Probabilistic Systems.
ACM Trans. Comput. Log., 2012

The Complexity of Non-Monotone Markets
CoRR, 2012

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
CoRR, 2012

Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
CoRR, 2012

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Computation of Least Fixed Points.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Market equilibrium under separable, piecewise-linear, concave utilities.
J. ACM, 2011

Temporal Synthesis for Bounded Systems and Environments.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010
On the Complexity of Nash Equilibria and Other Fixed Points.
SIAM J. Comput., 2010

An impossibility theorem for price-adjustment mechanisms.
Proc. Natl. Acad. Sci. U.S.A., 2010

Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems.
Perform. Eval., 2010

Computation of Equilibria and Stable Solutions.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

How Good is the Chord Algorithm?.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities.
Proceedings of the Innovations in Computer Science, 2010

2009
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems.
SIAM J. Comput., 2009

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.
J. ACM, 2009

Equilibria, fixed points, and complexity classes.
Computer Science Review, 2009

Computational Aspects of Equilibria.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

2008
Recursive Concurrent Stochastic Games.
Logical Methods in Computer Science, 2008

Multi-Objective Model Checking of Markov Decision Processes.
Logical Methods in Computer Science, 2008

Multi-Objective Model Checking of Markov Decision Processes
CoRR, 2008

Recursive Concurrent Stochastic Games
CoRR, 2008

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
CoRR, 2008

Equilibria, Fixed Points, and Complexity Classes
CoRR, 2008

Automata, Probability, and Recursion.
Proceedings of the Implementation and Applications of Automata, 2008

Equilibria, Fixed Points, and Complexity Classes.
Proceedings of the STACS 2008, 2008

Succinct approximate convex pareto curves.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems.
Proceedings of the Fifth International Conference on the Quantitative Evaluaiton of Systems (QEST 2008), 2008

Recursive Stochastic Games with Positive Rewards.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Multi-objective Model Checking of Markov Decision Processes.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2007

On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems.
Proceedings of the Approximation, 2007

2006
Adaptive Model Checking.
Logic Journal of the IGPL, 2006

Succinct Approximation of Trade-Off Curves.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.
Proceedings of the STACS 2006, 2006

A note on broadcast encryption key management with applications to large scale emergency alert systems.
Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006

Recursion and Probability.
Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Recursive Concurrent Stochastic Games.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Analysis of Recursive Probabilistic Models.
Proceedings of the Automated Technology for Verification and Analysis, 2006

2005
Analysis of recursive state machines.
ACM Trans. Program. Lang. Syst., 2005

Efficiently computing succinct trade-off curves.
Theor. Comput. Sci., 2005

Realizability and verification of MSC graphs.
Theor. Comput. Sci., 2005

Algorithmic Verification of Recursive Probabilistic State Machines.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2005

Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations.
Proceedings of the STACS 2005, 2005

Testing hierarchical systems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Checking LTL Properties of Recursive Markov Chains.
Proceedings of the Second International Conference on the Quantitative Evaluaiton of Systems (QEST 2005), 2005

Probability and Recursion.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Recursive Markov Decision Processes and Recursive Stochastic Games.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Guest Editors' foreword.
J. Comput. Syst. Sci., 2004

Multiway cuts in node weighted graphs.
J. Algorithms, 2004

Protocol System Integration, Interface and Interoperability.
Proceedings of the Principles of Distributed Systems, 8th International Conference, 2004

Testing, Optimizaton, and Games.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Efficiently Computing Succinct Trade-Off Curves.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Inference of Message Sequence Charts.
IEEE Trans. Software Eng., 2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.
J. Comput. Syst. Sci., 2003

Compression of Partially Ordered Strings.
Proceedings of the CONCUR 2003, 2003

2002
Closed Partition Lattice and Machine Decomposition.
IEEE Trans. Computers, 2002

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Review, 2002

Black Box Checking.
Journal of Automata, Languages and Combinatorics, 2002

Adaptive Model Checking.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2002

Testing and Checking of Finite State Systems.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

AMC: An Adaptive Model Checker.
Proceedings of the Computer Aided Verification, 14th International Conference, 2002

2001
Model checking of hierarchical state machines.
ACM Trans. Program. Lang. Syst., 2001

Approximation of Multiobjective Optimization Problems.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Multiobjective Query Optimization.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Realizability and Verification of MSC Graphs.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Analysis of Recursive State Machines.
Proceedings of the Computer Aided Verification, 13th International Conference, 2001

2000
Reminiscences on Influential Papers.
SIGMOD Record, 2000

Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discrete Math., 2000

Hierarchical State Machines.
Proceedings of the Theoretical Computer Science, 2000

Inference of message sequence charts.
Proceedings of the 22nd International Conference on on Software Engineering, 2000

From Rule-based to Automata-based Testing.
Proceedings of the Formal Techniques for Distributed System Development, 2000

On the Approximability of Trade-offs and Optimal Access of Web Sources.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
On the Complexity of Database Queries.
J. Comput. Syst. Sci., 1999

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

A Convex Relaxation for the Asymmetric TSP.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Communicating Hierarchical State Machines.
Proceedings of the Automata, 1999

Black Box Checking.
Proceedings of the Formal Methods for Protocol Engineering and Distributed Systems, 1999

Model Checking of Message Sequence Charts.
Proceedings of the CONCUR '99: Concurrency Theory, 1999

1998
On the Complexity of Protein Folding.
Journal of Computational Biology, 1998

On the Complexity of Protein Folding (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Model Checking of Hierarchical State Machines.
Proceedings of the SIGSOFT '98, 1998

On the complexity of protein folding (abstract).
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Protocol Feature Interactions.
Proceedings of the Formal Description Techniques and Protocol Specification, 1998

Testing for Finite State Systems.
Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997
Tie-Breaking Semantics and Structural Totality.
J. Comput. Syst. Sci., 1997

An Efficient Algorithm for Minimizing Real-Time Transition Systems.
Formal Methods in System Design, 1997

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees.
Algorithmica, 1997

On the Complexity of Database Queries.
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

Existence of Reduction Hierarchies.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
Perspectives on database theory.
SIGACT News, 1996

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications.
SIAM J. Comput., 1996

On Limited Nondeterminism and the Complexity of the V-C Dimension.
J. Comput. Syst. Sci., 1996

Optimization problems from feature testing of communication protocols.
Proceedings of the 1996 International Conference on Network Protocols, 1996

Searching a Fixed Graph.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

On nested depth first search.
Proceedings of the Spin Verification System, 1996

1995
Timing Verification by Successive Approximation
Inf. Comput., April, 1995

Testing Finite State Machines: Fault Detection.
J. Comput. Syst. Sci., 1995

On Datalog vs. Polynomial Time.
J. Comput. Syst. Sci., 1995

The Complexity of Probabilistic Verification.
J. ACM, 1995

Distinguishing tests for nondeterministic and probabilistic machines.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Perspectives on Database Theory.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Testing Finite-State Machines: State Identification and Verification.
IEEE Trans. Computers, 1994

The Complexity of Multiterminal Cuts.
SIAM J. Comput., 1994

On the Approximation of Maximum Satisfiability.
J. Algorithms, 1994

On the Hardness of Approximating Minimization Problems.
J. ACM, 1994

Linear Approximation of Shortest Superstrings.
J. ACM, 1994

On complexity as bounded rationality (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Multiway Cuts in Directed and Node Weighted Graphs.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Some Open Problems in Approximation.
Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993
The Traveling Salesman Problem with Distances One and Two.
Math. Oper. Res., 1993

Computing the Throughput of a Network with Dedicated Lines.
Discrete Applied Mathematics, 1993

Linear programming without the matrix.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On the hardness of approximating minimization problems.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Approximate max-flow min-(multi)cut theorems and their applications.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Recent Developments on the Approximability of Combinatorial Problems.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

The Approximation of Maximum Subgraph Problems.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

An Efficient Algorithm for Minimizing Real-time Transition Systems.
Proceedings of the Computer Aided Verification, 5th International Conference, 1993

1992
Minimum and Maximum Delay Problems in Real-Time Systems.
Formal Methods in System Design, 1992

Memory-Efficient Algorithms for the Verification of Temporal Properties.
Formal Methods in System Design, 1992

Online Minimization of Transition Systems (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

The Complexity of Multiway Cuts (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Approximation of Maximum Satisfiability.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Tie-Breaking Semantics and Structural Totality.
Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1992

Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Timing Verification by Successive Approximation.
Proceedings of the Computer Aided Verification, Fourth International Workshop, 1992

1991
Shortest Paths Without a Map.
Theor. Comput. Sci., 1991

High-Probability Parallel Transitive-Closure Algorithms.
SIAM J. Comput., 1991

Simple Local Search Problems That are Hard to Solve.
SIAM J. Comput., 1991

Expressing Combinatorial Optimization Problems by Linear Programs.
J. Comput. Syst. Sci., 1991

Optimization, Approximation, and Complexity Classes.
J. Comput. Syst. Sci., 1991

Modularity of Cycles and Paths in Graphs.
J. ACM, 1991

The Input/Output Complexity of Transitive Closure.
Ann. Math. Artif. Intell., 1991

Testing Finite State Machines (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Linear Approximation of Shortest Superstrings
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

On Datalog vs. Polynomial Time.
Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1991

On the Value of Information in Distributed Decision-Making (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

1990
Towards an Architecture-Independent Analysis of Parallel Algorithms.
SIAM J. Comput., 1990

On recognizing integer polyhedra.
Combinatorica, 1990

On the Complexity of Local Search (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

The Analysis of Local Search Problems and Their Heuristics.
Proceedings of the STACS 90, 1990

High-Probability Parallel Transitive Closure Algorithms.
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

The Input/Output Complexity of Transitive Closure.
Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 1990

Graph-Theoretic Methods in Database Theory.
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1990

Markov Decision Processes and Regular Events (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Memory Efficient Algorithms for the Verification of Temporal Properties.
Proceedings of the Computer-Aided Verification, 1990

1989
Embedding Planar Graphs in Four Pages.
J. Comput. Syst. Sci., 1989

Deleting Completed Transactions.
J. Comput. Syst. Sci., 1989

Optimal Scheduling of Products with Two Subassemblies on a Single Machine.
Operations Research, 1989

Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs.
Discrete Applied Mathematics, 1989

Shortest Paths Without a Map.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988
How Easy is Local Search?
J. Comput. Syst. Sci., 1988

On Generating All Maximal Independent Sets.
Inf. Process. Lett., 1988

Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Optimization, Approximation, and Complexity Classes (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Verifying Temporal Properties of Finite-State Probabilistic Programs
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
The Complexity of Reliable Concurrency Control.
SIAM J. Comput., 1987

The Maximum k-Colorable Subgraph Problem for Chordal Graphs.
Inf. Process. Lett., 1987

1986
A Note on Succinct Representations of Graphs
Information and Control, December, 1986

Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
J. Comput. Syst. Sci., 1986

Querying Weak Instances.
Advances in Computing Research, 1986

Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Deleting Completed Transactions.
Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1986

Linear and Book Embeddings of Graphs.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees
J. ACM, October, 1985

Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput., 1985

On a Class of Totally Unimodular Matrices.
Math. Oper. Res., 1985

Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1985

The Complexity of Reliable Concurrency Control.
Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1985

How Easy Is Local Search? (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput., 1984

Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum.
Math. Oper. Res., 1984

The Complexity of Facets (and Some Facets of Complexity).
J. Comput. Syst. Sci., 1984

Independent Database Schemas.
J. Comput. Syst. Sci., 1984

Serializability by Locking.
J. ACM, 1984

On Monotone Formulae with Restricted Depth (Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Querying Weak Instances.
Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1984

1983
On the Desirability of Acyclic Database Schemes
J. ACM, July, 1983

Tools for Template Dependencies.
SIAM J. Comput., 1983

On Notions of Information Transfer in VLSI Circuits
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract).
Proceedings of the Automata, 1983

A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
Freedom from Deadlock of Safe Locking Policies.
SIAM J. Comput., 1982

Algebraic Dependencies.
J. Comput. Syst. Sci., 1982

A Theory of Safe Locking Policies in Database Systems.
J. ACM, 1982

The complexity of restricted spanning tree problems.
J. ACM, 1982

The Complexity of Facets (and Some Facets of Complexity)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Independent Database Schemas.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

1981
Node-Deletion Problems on Bipartite Graphs.
SIAM J. Comput., 1981

Edge-Deletion Problems.
SIAM J. Comput., 1981

On the Complexity of Testing Implications of Functional and Join Dependencies.
J. ACM, 1981

The Clique Problem for Planar Graphs.
Inf. Process. Lett., 1981

On Minimal Eulerian Graphs.
Inf. Process. Lett., 1981

The Complexity of Testing Whether a Graph is a Superconcentrator.
Inf. Process. Lett., 1981

Algorithms for Acyclic Database Schemes
Proceedings of the Very Large Data Bases, 1981

Issues of Correctness in Database Concurrency Control by Locking
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Properties of Acyclic Database Schemes
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
The Node-Deletion Problem for Hereditary Properties is NP-Complete.
J. Comput. Syst. Sci., 1980

Equivalences Among Relational Expressions with the Union and Difference Operators.
J. ACM, 1980

Testing the Universal Instance Assumption.
Inf. Process. Lett., 1980

Algebraic Dependencies (Extended Abstract)
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

On a Class of Totally Unimodular Matrices
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
Topological Characterization of Families of Graphs Generated by Certain Types of Graph Grammars
Information and Control, July, 1979

Scheduling Interval-Ordered Tasks.
SIAM J. Comput., 1979

The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems.
J. ACM, 1979

The Complexity of Restricted Minimum Spanning Tree Problems (Extended Abstract).
Proceedings of the Automata, 1979

Locking Policies: Safety and Freedom from Deadlock
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

Modeling Communications Protocols by Automata
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Equivalence among Relational Expressions with the Union and Difference Operation.
Proceedings of the Fourth International Conference on Very Large Data Bases, 1978

Node- and Edge-Deletion NP-Complete Problems
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978


  Loading...