@article{Bagchi-Mahanti/85,
AUTHOR = {Bagchi, A. and Mahanti, A.},
TITLE = {Three approaches to heuristic search in networks},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {1-27},
YEAR = {1985},
KEYWORDS = {Admissible heuristic, inadmissible heuristic, propagation, arc marking, search graph},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Mahanti-Bagchi/85,
AUTHOR = {Mahanti, A. and Bagchi, A.},
TITLE = {AND/OR graph heuristic search methods},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {28-51},
YEAR = {1985},
KEYWORDS = {Admissible heuristic, solution graph, potential solution graph, discriminant, sumcost, maxcost},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lamport-Melliar-Smith/85,
AUTHOR = {Lamport, L. and Melliar-Smith, P.M.},
TITLE = {Synchronizing clocks in the presence of faults},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {52-78},
YEAR = {1985},
KEYWORDS = {Byzantine failures, synchronization},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Abiteboul/85,
AUTHOR = {Abiteboul, S.},
TITLE = {Disaggregations in databases},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {79-101},
YEAR = {1985},
KEYWORDS = {Disaggregation, free families, dependency families, matching functions, (embedded) functional dependencies, join dependencies},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fuchs-Kafura/85,
AUTHOR = {Fuchs, K. and Kafura, D.},
TITLE = {Memory-constrained task scheduling on a network of dual processors},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {102-129},
YEAR = {1985},
KEYWORDS = {Deterministic scheduling, scheduling algorithms, memory management, largest-memory-first, shared memory, networks of processors},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hochbaum-Maass/85,
AUTHOR = {Hochbaum, D.S. and Maass, W.},
TITLE = {Approximation schemes for covering and packing problems in image processing and VLSI},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {130-136},
YEAR = {1985},
KEYWORDS = {Covering, packing, covering points in the Euclidean space, image processing, VLSI, shifting strategy, worst case analysis of heuristics, polynomial approximation scheme},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hennessy-Milner/85,
AUTHOR = {Hennessy, M. and Milner, R.},
TITLE = {Algebraic laws for nondeterminism and concurrency},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {137-161},
YEAR = {1985},
KEYWORDS = {Communicating processes, observational equivalence},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Vantilborgh/85,
AUTHOR = {Vantilborgh, H.},
TITLE = {Aggregation with an error of $O(\epsilon^2)$},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {162-190},
YEAR = {1985},
KEYWORDS = {Approximation, near-complete decomposability, queuing network, aggregation, multiprogramming system},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Dolev-Reischuk/85,
AUTHOR = {Dolev, D. and Reischuk, R.},
TITLE = {Bounds on information exchange for Byzantine agreement},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {191-204},
YEAR = {1985},
KEYWORDS = {Distributed systems, reliability, Byzantine agreement},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Even-Selman-Yacobi/85,
AUTHOR = {Even, S. and Selman, A.L. and Yacobi, Y.},
TITLE = {Hard-core theorems for complexity classes},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {205-217},
YEAR = {1985},
KEYWORDS = {Hard-core, complexity core, randomized computation},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Klawe/85,
AUTHOR = {Klawe, M.M.},
TITLE = {A tight bound for black and white pebbles on the pyramid},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {218-228},
YEAR = {1985},
KEYWORDS = {Pebbling, pyramid, lower bound, nondeterminism},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lagarias-Odlyzko/85,
AUTHOR = {Lagarias, J.C. and Odlyzko, A.M.},
TITLE = {Solving low-density subset sum problems},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {1},
PAGES = {229-246},
YEAR = {1985},
KEYWORDS = {Knapsack public-key cryptosystem, subset sum problems, integer lattice, $L^3$ algorithm},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bauer/85a,
AUTHOR = {Bauer, M.A.},
TITLE = {Soundness and completeness of a synthesis algorithm based on example computations},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {249-279},
YEAR = {1985},
KEYWORDS = {Programming by example},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gottlob-Leitsch/85a,
AUTHOR = {Gottlob, G. and Leitsch, A.},
TITLE = {On the efficiency of subsumption algorithms},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {280-295},
YEAR = {1985},
KEYWORDS = {Complexity estimation, new algorithm, subsumption},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Wang-Lloyd-Soffa/85,
AUTHOR = {Wang, C.-C. and Lloyd, E.L. and Soffa, M.L.},
TITLE = {Feedback vertex sets and cyclically reducible graphs},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {296-313},
YEAR = {1985},
KEYWORDS = {Deadlock, feedback vertex set, reducible flow graph, NP-complete problem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Buckley-Silberschatz/85,
AUTHOR = {Buckley, G.N. and Silberschatz, A.},
TITLE = {Beyond two-phase locking},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {314-326},
YEAR = {1985},
KEYWORDS = {Concurrency, consistency, database systems, deadlocks, hypergraphs, locking protocols, serializability, transactions},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Baker-Coffman-Willard/85,
AUTHOR = {Baker, B.S. and Coffman, E.G., Jr. and Willard, D.E.},
TITLE = {Algorithms for resolving conflicts in dynamic storage allocation},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {327-343},
YEAR = {1985},
KEYWORDS = {Buddy system, dynamic storage allocation, fragmentation of memory},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gonzalez-Smith-Storer/85,
AUTHOR = {Gonzalez-Smith, M.E. and Storer, J.A.},
TITLE = {Parallel algorithms for data compression},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {344-373},
YEAR = {1985},
KEYWORDS = {Data compression, textual substitution, VLSI, parallel algorithm, distributed processors},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fischer-Lynch-Paterson/85,
AUTHOR = {Fischer, M.J. and Lynch, N.A. and Paterson, M.S.},
TITLE = {Impossibility of distributed consensus with one faulty process},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {374-382},
YEAR = {1985},
KEYWORDS = {Agreement problem, asynchronous system, Byzantine Generals problem, commit problem, consensus problem, distributed computing, fault tolerance, impossibility proof, reliability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Cornuejols-Naddef-Pulleyblank/85,
AUTHOR = {Cornu{\'e}jols, G. and Naddef, D. and Pulleyblank, W.},
TITLE = {The traveling salesman problem in graphs with 3-edge cutsets},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {383-410},
YEAR = {1985},
KEYWORDS = {Traveling salesman problem, polynomial algorithms, graph decompositions, integer polytopes, Halin graphs},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Staples-Nguyen/85,
AUTHOR = {Staples, J. and Nguyen, V.L.},
TITLE = {A fixpoint semantics for nondeterministic data flow},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {411-444},
YEAR = {1985},
KEYWORDS = {Asynchronous, data flow, denotational, nondeterminism, semantics},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Tantawi-Towsley/85,
AUTHOR = {Tantawi, A.N. and Towsley, D.},
TITLE = {Optimal static load balancing in distributed computer systems},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {445-465},
YEAR = {1985},
KEYWORDS = {Distributed computer systems, optimal load balancing, parametric-study algorithm, performance modeling and optimization, single-point algorithm},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gurari/85,
AUTHOR = {Gurari, E.M.},
TITLE = {Decidable problems for powerful programs},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {466-483},
YEAR = {1985},
KEYWORDS = {Simple programming languages, equivalence problem, computational complexity, decidable, undecidable, PSPACE-complete, Presburger sets, counter machines},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Skyum-Valiant/85,
AUTHOR = {Skyum, S. and Valiant, L.G.},
TITLE = {A complexity theory based on Boolean algebra},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {2},
PAGES = {484-502},
YEAR = {1985},
KEYWORDS = {Boolean functions, circuit complexity, complexity classes, NP-completeness, projections},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Dechter-Pearl/85,
AUTHOR = {Dechter, R. and Pearl, J.},
TITLE = {Generalized best first search strategies and the optimality of A*},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {505-536},
YEAR = {1985},
KEYWORDS = {Best-first strategies, branch and bound, heuristic search, shortest path algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bender-Butler/85,
AUTHOR = {Bender, E.A. and Butler, J.T.},
TITLE = {Enumeration of structured flowcharts},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {537-548},
YEAR = {1985},
KEYWORDS = {BJ-charts, D-charts, decision node, flowchart enumeration, sequency, structured programming},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Cunningham/85,
AUTHOR = {Cunningham, W.H.},
TITLE = {Optimal attack and reinforcement of a network},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {549-561},
YEAR = {1985},
KEYWORDS = {Greedy algorithm, minimum cuts, networks, polymatroids, ratio minimization, strongly polynomial algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lee-Lee/85,
AUTHOR = {Lee, C.C. and Lee, D.T.},
TITLE = {A simple on-line packing algorithm},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {562-572},
YEAR = {1985},
KEYWORDS = {Bin packing, on line, suboptimal algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chazelle-Monier/85,
AUTHOR = {Chazelle, B. and Monier, L.},
TITLE = {A model of computation for VLSI with related complexity results},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {573-588},
YEAR = {1985},
KEYWORDS = {Chip complexity, lower bounds},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Greenberg-Winograd/85,
AUTHOR = {Greenberg, A.G. and Winograd, S.},
TITLE = {A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {589-596},
YEAR = {1985},
KEYWORDS = {Conflict resolution, multiple access channels},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Willard-Lueker/85,
AUTHOR = {Willard, D.E. and Lueker, G.S.},
TITLE = {Adding range restriction capability to dynamic data structures},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {597-617},
YEAR = {1985},
KEYWORDS = {Decomposable searching problems, empirical cumulative distribution function, range queries, trees of bounded balance},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Tay-Suri-Goodman/85,
AUTHOR = {Tay, Y.C. and Suri, R. and Goodman, N.},
TITLE = {A mean value performance model for locking in databases: The no-waiting case},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {618-651},
YEAR = {1985},
KEYWORDS = {Concurrency control, database locking, data contention, resource contention, shared data},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sleator-Tarjan/85,
AUTHOR = {Sleator, D.D. and Tarjan, R.E.},
TITLE = {Self-adjusting binary search trees},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {652-686},
YEAR = {1985},
KEYWORDS = {Amortized complexity, balanced trees, multidimensional searching, network optimization, self-organizing data structures},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Yao/85a,
AUTHOR = {Yao, A.C.},
TITLE = {Uniform hashing is optimal},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {687-693},
YEAR = {1985},
KEYWORDS = {Hashing, hashing function, optimality, uniform hashing},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Zerling/85,
AUTHOR = {Zerling, D.},
TITLE = {Generating binary trees using rotations},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {694-701},
YEAR = {1985},
KEYWORDS = {Backtracking, binary tree, codewords, extended binary trees, full binary trees, generating binary trees, lattice paths, level number, rotating, unconstrained backtracking},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Cao-Stewart/85,
AUTHOR = {Cao, W.-L. and Stewart, W.J.},
TITLE = {Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {702-719},
YEAR = {1985},
KEYWORDS = {Aggregation/disaggregation, decomposability, eigenvalues, Markov chains, stationary probability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Manber-Tompa/85,
AUTHOR = {Manber, U. and Tompa, M.},
TITLE = {The complexity of problems on probabilistic, nondeterministic, and alternating decision trees},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {720-732},
YEAR = {1985},
KEYWORDS = {Computational complexity, decision trees, lower bounds, Monte Carlo algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sistla-Clarke/85,
AUTHOR = {Sistla, A.P. and Clarke, E.M.},
TITLE = {The complexity of propositional linear temporal logics},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {3},
PAGES = {733-749},
YEAR = {1985},
KEYWORDS = {Branching time temporal logic, decision procedures, linear time temporal logic, NP-complete, PSPACE-complete, satisfiability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Freuder/85,
AUTHOR = {Freuder, E.C.},
TITLE = {A sufficient condition for backtrack-bounded search},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {755-761},
YEAR = {1985},
KEYWORDS = {Biconnected component, constraint consistency, constraint networks, constraint satisfaction, relaxation, width},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Karp-Wigderson/85,
AUTHOR = {Karp, R.M. and Wigderson, A.},
TITLE = {A fast parallel algorithm for the maximal independent set problem},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {762-773},
YEAR = {1985},
KEYWORDS = {Block designs, graph theory, independent sets, parallel computation},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sacca/85,
AUTHOR = {Sacc{\`a}, D.},
TITLE = {Closures of database hypergraphs},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {774-803},
YEAR = {1985},
KEYWORDS = {Acyclic, closure, computational complexity, functional dependency, hypergraph, independent, join dependency,$NP$-complete, relational database},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Awerbuch/85,
AUTHOR = {Awerbuch, B.},
TITLE = {Complexity of network synchronization},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {804-823},
YEAR = {1985},
KEYWORDS = {Communication and time complexities, distributed algorithms, networks, synchronization},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bracha-Toueg/85,
AUTHOR = {Bracha, G. and Toueg, S.},
TITLE = {Asynchronous consensus and broadcast protocols},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {824-840},
YEAR = {1985},
KEYWORDS = {Agreement problem, asynchronous system, Byzantine Generals problem, consensus problem, distributed computing, fault tolerance, impossibility proof, probabilistic algorithms, reliability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Garcia-Molina-Barbara/85,
AUTHOR = {Garcia-Molina, H. and Barbara, D.},
TITLE = {How to assign votes in a distributed system},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {841-860},
YEAR = {1985},
KEYWORDS = {Distributed databases, mutual exclusion, partitions},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Faigle/85,
AUTHOR = {Faigle, U.},
TITLE = {On ordered languages and the optimization of linear functions by greedy algorithms},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {861-870},
YEAR = {1985},
KEYWORDS = {Greedy algorithms, hereditary language, linear function, ordered matroid, rank function},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Adler-Meggido/85,
AUTHOR = {Adler, I. and Meggido, N.},
TITLE = {A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {871-895},
YEAR = {1985},
KEYWORDS = {Lexicographic pivoting, probabilistic analysis of algorithms, simplex algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hennessy/85,
AUTHOR = {Hennessy, M.},
TITLE = {Acceptance trees},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {896-928},
YEAR = {1985},
KEYWORDS = {Axioms, nondeterministic machines, testing equivalence, trees},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Meyer_auf_der_Heide/85b,
AUTHOR = {Meyer auf der Heide, F.},
TITLE = {Lower bounds for solving linear Diophantine equations on random access machines},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {929-937},
YEAR = {1985},
KEYWORDS = {Integer programming, linear search algorithms, random access machines},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Moran-Snir-Manber/85,
AUTHOR = {Moran, Shlomo and Snir, Marc and Manber, Udi},
TITLE = {Applications of Ramsey's theorem to decision tree complexity},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {938-949},
YEAR = {1985},
KEYWORDS = {Computational complexity, decision trees, lower bounds, Ramsey's theorem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Yannakakis/85,
AUTHOR = {Yannakakis, M.},
TITLE = {A polynomial algorithm for the min-cut linear arrangement of trees},
JOURNAL = {J. ACM},
VOLUME = {32},
NUMBER = {4},
PAGES = {950-988},
YEAR = {1985},
KEYWORDS = {Cutwidth, min-cut linear arrangement, pebbling},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}