×

Journal of the Association for Computing Machinery

Short Title: J. Assoc. Comput. Mach.
Publisher: Association for Computing Machinery (ACM), New York, NY
ISSN: 0004-5411
Online: http://dl.acm.org/citation.cfm?id=J401
Successor: Journal of the ACM
Comments: Journal; No longer indexed
Documents Indexed: 1,779 Publications (1955–1995)
References Indexed: 15 Publications with 169 References.
all top 5

Authors

21 Ginsburg, Seymour
18 Tarjan, Robert Endre
15 Papadimitriou, Christos Harilaos
15 Ullman, Jeffrey David
12 Coffman, Edward Grady jun.
12 Halpern, Joseph Yehuda
12 Lynch, Nancy Ann
12 Yannakakis, Mihalis
11 Galil, Zvi
11 Rosenberg, Arnold Leonard
11 Sahni, Sartaj K.
10 Fagin, Ronald
10 Slagle, James R.
9 Dolev, Danny
9 Harrison, Michael A.
9 Ibarra, Oscar H.
9 Kung, H. T.
9 Winograd, Shmuel
9 Yao, Andrew Chi-Chih
8 Fischer, Michael J.
8 Sagiv, Yehoshua
8 Traub, Joseph Frederick
7 Adiri, Igal
7 Aho, Alfred Vaino
7 Greibach, Sheila A.
7 Hopcroft, John Edward H.
7 Hunt, Harry Bowen III
7 Karp, Richard Manning
7 Konheim, Alan G.
7 Megiddo, Nimrod
7 Salton, Gerard
7 Stockmeyer, Larry J.
7 Towsley, Donald Fred
7 Valiant, Leslie Gabriel
7 Wong, Chak-Kuen
7 Yu, Clement T.
6 Attiya, Hagit
6 Curtis, H. Allen
6 Garey, Michael Randolph
6 Hibbard, Thomas N.
6 Lipton, Richard Jay
6 Meyer, Albert Ronald
6 Mitra, Debasis
6 Sethi, Ravi
5 Brent, Richard Peirce
5 Bruno, John L.
5 Chaitin, Gregory John
5 Dwork, Cynthia
5 Even, Shimon
5 Frederickson, Greg N.
5 Gelenbe, Sami Erol
5 Gonzalez, Teofilo F.
5 Hartmanis, Juris
5 Iglehart, Donald Lee
5 Johnson, Donald B.
5 Kleinrock, Leonard
5 Lamport, Leslie
5 Loveland, Donald W.
5 Manna, Zohar
5 Muntz, Richard R.
5 Pease, Marshall C. III
5 Peleg, David
5 Pippenger, Nicholas J.
5 Preparata, Franco P.
5 Reif, John H.
5 Reischuk, Rüdiger
5 Shostak, Robert E.
5 Upfal, Eli
5 Vardi, Moshe Ya’akov
5 Wagner, Robert A.
5 Wigderson, Avi
4 Baccelli, François Louis
4 Baker, Brenda S.
4 Beeri, Catriel
4 Blum, Manuel
4 Book, Ronald Vernon
4 Brzozowski, Janusz Antoni
4 Chandy, Kanianthra Mani
4 Chazelle, Bernard
4 Ehrenfeucht, Andrzej
4 Fischer, Patrick Carl
4 Fredman, Michael L.
4 Gabow, Harold N.
4 Gill, Arthur
4 Gottlob, Georg
4 Gurari, Eitan M.
4 Hennessy, Matthew C. B.
4 Henschen, Lawrence J.
4 Hirschberg, Daniel S.
4 Hofri, Micha
4 Horowitz, Ellis
4 Ja’Ja’, Joseph F.
4 Johnson, David Stifler
4 Kannan, Ravindran
4 Kosaraju, S. Rao
4 Ladner, Richard E.
4 Lavenberg, Stephen S.
4 Maier, David
4 Mansour, Yishay
4 Mehlhorn, Kurt
...and 1,681 more Authors
all top 5

Fields

1,088 Computer science (68-XX)
154 Numerical analysis (65-XX)
122 Mathematical logic and foundations (03-XX)
119 Operations research, mathematical programming (90-XX)
92 Information and communication theory, circuits (94-XX)
82 Combinatorics (05-XX)
58 Probability theory and stochastic processes (60-XX)
20 Linear and multilinear algebra; matrix theory (15-XX)
19 Number theory (11-XX)
11 Group theory and generalizations (20-XX)
10 Field theory and polynomials (12-XX)
9 Statistics (62-XX)
8 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
7 Convex and discrete geometry (52-XX)
6 Systems theory; control (93-XX)
5 General algebraic systems (08-XX)
5 Approximations and expansions (41-XX)
4 Biology and other natural sciences (92-XX)
3 Order, lattices, ordered algebraic structures (06-XX)
3 Real functions (26-XX)
3 Harmonic analysis on Euclidean spaces (42-XX)
3 Integral equations (45-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
2 History and biography (01-XX)
2 Associative rings and algebras (16-XX)
2 Functions of a complex variable (30-XX)
2 Ordinary differential equations (34-XX)
2 Partial differential equations (35-XX)
2 Operator theory (47-XX)
1 Commutative algebra (13-XX)
1 Nonassociative rings and algebras (17-XX)
1 Integral transforms, operational calculus (44-XX)
1 Geometry (51-XX)
1 General topology (54-XX)
1 Algebraic topology (55-XX)
1 Manifolds and cell complexes (57-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of particles and systems (70-XX)
1 Geophysics (86-XX)

Publications by Year

Citations contained in zbMATH Open

1,556 Publications have been cited 47,268 times in 34,655 Documents Cited by Year
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088
Goemans, Michel X.; Williamson, David P.
771
1995
A machine-oriented logic based on the resolution principle. Zbl 0139.12303
Robinson, J. A.
631
1965
Impossibility of distributed consensus with one faulty process. Zbl 0629.68027
Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S.
562
1985
Alternation. Zbl 0473.68043
Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J.
560
1981
A computing procedure for quantification theory. Zbl 0212.34203
Davis, M.; Putnam, H.
443
1960
Fast probabilistic algorithms for verification of polynomial identities. Zbl 0452.68050
Schwartz, J. T.
435
1980
Theoretical improvements in algorithmic efficiency for network flow problems. Zbl 0318.90024
Edmonds, Jack; Karp, Richard M.
417
1972
Fibonacci heaps and their uses in improved network optimization algorithms. Zbl 1412.68048
Fredman, Michael L.; Tarjan, Robert Endre
386
1987
Integer programming formulation of traveling salesman problems. Zbl 0100.15101
Miller, C. E.; Tucker, A. W.; Zemlin, R. A.
373
1960
Optimal order of one-point and multipoint iteration. Zbl 0289.65023
Kung, H. T.; Traub, J. F.
369
1974
Confluent reductions: Abstract properties and applications to term rewriting systems. Zbl 0458.68007
Huet, Gerard
369
1980
Algebraic laws for nondeterminism and concurrency. Zbl 0629.68021
Hennessy, Matthew; Milner, Robin
362
1985
Scheduling algorithms for multiprogramming in a hard-real-time environment. Zbl 0265.68013
Liu, C. L.; Layland, James W.
362
1973
Reaching agreement in the presence of faults. Zbl 0434.68031
Pease, M.; Shostak, R.; Lamport, L.
358
1980
Color-coding. Zbl 0885.68116
Alon, Noga; Yuster, Raphael; Zwick, Uri
355
1995
Efficient planarity testing. Zbl 0307.68025
Hopcroft, John; Tarjan, Robert
343
1974
P-complete approximation problems. Zbl 0348.90152
Sahni, Sartaj; Gonzalez, Teofilo
338
1976
Learnability and the Vapnik-Chervonenkis dimension. Zbl 0697.68079
Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K.
329
1989
A new approach to the maximum-flow problem. Zbl 0661.90031
Goldberg, Andrew V.; Tarjan, Robert E.
311
1988
’Direct search’ solution of numerical and statistical problems. Zbl 0111.12501
Hooke, R.; Jeeves, T. A.
289
1961
On context-free languages. Zbl 0154.25801
Parikh, R. J.
286
1966
The string-to-string correction problem. Zbl 0278.68032
Wagner, Robert A.; Fischer, Michael J.
282
1974
The well-founded semantics for general logic programs. Zbl 0799.68045
Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S.
280
1991
Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067
Baker, Brenda S.
277
1994
Fast approximation algorithms for the knapsack and sum of subset problems. Zbl 0345.90049
Ibarra, Oscar H.; Kim, Chul E.
276
1975
The semantics of predicate logic as a programming language. Zbl 0339.68004
van Emden, M. H.; Kowalski, R. A.
264
1976
A theory of communicating sequential processes. Zbl 0628.68025
Brookes, S. D.; Hoare, C. A. R.; Roscoe, A. W.
261
1984
Open, closed, and mixed networks of queues with different classes of customers. Zbl 0313.68055
Baskett, Forest; Chandy, K. Mani; Muntz, Richard R.; Palacios, Fernando G.
257
1975
A machine-independent theory of the complexity of recursive functions. Zbl 0155.01503
Blum, Manuel
255
1967
A framework for defining logics. Zbl 0778.03004
Harper, Robert; Honsell, Furio; Plotkin, Gordon
251
1993
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Zbl 0799.68101
Goldreich, Oded; Micali, Silvio; Wigderson, Avi
245
1991
The complexity of propositional linear temporal logics. Zbl 0632.68034
Sistla, A. P.; Clarke, E. M.
245
1985
Efficiency of a good but not linear set union algorithm. Zbl 0307.68029
Tarjan, Robert Endre
242
1975
A technique for the numerical solution of certain integral equations of the first kind. Zbl 0108.29902
Phillips, D. L.
242
1962
Institutions: Abstract model theory for specification and programming. Zbl 0799.68134
Goguen, Joseph A.; Burstall, Rod M.
238
1992
“Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035
Garey, M. R.; Johnson, D. S.
238
1978
Initial algebra semantics and continuous algebras. Zbl 0359.68018
Goguen, J. A.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B.
229
1977
Open shop scheduling to minimize finish time. Zbl 0343.68031
Gonzalez, Teofilo; Sahni, Sartaj
223
1976
Derivatives of regular expressions. Zbl 0225.94044
Brzozowski, Janusz A.
222
1964
A theorem on Boolean matrices. Zbl 0118.33104
Warshall, S.
220
1962
Applying parallel computation algorithms in the design of serial algorithms. Zbl 0627.68034
Megiddo, Nimrod
218
1983
“Sometimes” and “not never” revisited: On branching versus linear time temporal logic. Zbl 0629.68020
Emerson, E. Allen; Halpern, Joseph Y.
216
1986
Iterative procedures for nonlinear integral equations. Zbl 0149.11503
Anderson, D. G.
214
1965
A space-economical suffix tree construction algorithm. Zbl 0329.68042
McCreight, Edward M.
211
1976
A theory of program size formally identical to information theory. Zbl 0309.68045
Chaitin, Gregory J.
209
1975
On the hardness of approximating minimization problems. Zbl 0814.68064
Lund, Carsten; Yannakakis, Mihalis
208
1994
Approximation schemes for covering and packing problems in image processing and VLSI. Zbl 0633.68027
Hochbaum, Dorit S.; Maass, Wolfgang
208
1985
On the structure of polynomial time reducibility. Zbl 0322.68028
Ladner, Richard E.
208
1975
On the desirability of acyclic database schemes. Zbl 0624.68087
Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis
204
1983
Reversal-bounded multicounter machines and their decision problems. Zbl 0365.68059
Ibarra, Oscar H.
188
1978
Storing a sparse table with O(1) worst case access time. Zbl 0629.68068
Fredman, Michael L.; Komlós, János; Szemerédi, Endre
188
1984
Self-adjusting binary search trees. Zbl 0631.68060
Sleator, Daniel Dominic; Tarjan, Robert Endre
184
1985
Knowledge and common knowledge in a distributed environment. Zbl 0699.68115
Halpern, Joseph Y.; Moses, Yoram
181
1990
Algorithms for scheduling independent tasks. Zbl 0326.68024
Sahni, Sartaj K.
181
1976
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
175
1992
A fast direct solution of Poisson’s equation using Fourier analysis. Zbl 0139.10902
Hockney, R. W.
171
1965
Linear programming in linear time when the dimension is fixed. Zbl 0637.90064
Megiddo, Nimrod
163
1984
A random polynomial-time algorithm for approximating the volume of convex bodies. Zbl 0799.68107
Dyer, Martin; Frieze, Alan; Kannan, Ravi
162
1991
Complexity of network synchronization. Zbl 0628.68045
Awerbuch, Baruch
162
1985
A transformation system for developing recursive programs. Zbl 0343.68014
Burstall, R. M.; Darlington, John
162
1977
On communicating finite-state machines. Zbl 0512.68039
Brand, Daniel; Zafiropulo, Pitro
160
1983
Parallel prefix computation. Zbl 0445.68066
Ladner, Richard E.; Fischer, Michael J.
160
1980
The parallel evaluation of general arithmetic expressions. Zbl 0276.68010
Brent, Richard P.
158
1974
Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006
Linial, Nathan; Mansour, Yishay; Nisan, Noam
157
1993
Bisimulation can’t be traced. Zbl 0886.68027
Bloom, Bard; Istrail, Sorin; Meyer, Albert R.
155
1995
On the length of programs for computing finite binary sequences. Zbl 0158.25301
Chaitin, Gregory J.
150
1966
Indexed grammars - an extension of context-free grammars. Zbl 0175.27801
Aho, A. V.
148
1968
Dynamic programming treatment of the travelling salesman problem. Zbl 0106.14102
Bellman, Richard
146
1962
\(\mathrm{IP}=\mathrm{PSPACE}\). Zbl 0799.68096
Shamir, Adi
141
1992
Atomic snapshots of shared memory. Zbl 0783.68029
Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir
134
1993
Complete sets of reductions for some equational theories. Zbl 0479.68092
Peterson, Gerald E.; Stickel, Mark E.
133
1981
Hard examples for resolution. Zbl 0639.68093
Urquhart, Alasdair
131
1987
Efficient algorithms for shortest paths in sparse networks. Zbl 0343.68028
Johnson, Donald B.
131
1977
Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0222.02035
Cook, Stephen A.
130
1971
The complexity of probabilistic verification. Zbl 0885.68109
Courcoubetis, Costas; Yannakakis, Mihalis
129
1995
The complexity of some problems on subsequences and supersequences. Zbl 0371.68018
Maier, David
128
1978
The complexity of searching a graph. Zbl 0637.68081
Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H.
128
1988
Computing partitions with applications to the knapsack problem. Zbl 0329.90046
Horowitz, Ellis; Sahni, Sartaj
125
1974
A simple on-line bin-packing algorithm. Zbl 0629.68045
Lee, C. C.; Lee, D. T.
122
1985
Slowing down sorting networks to obtain faster sorting algorithms. Zbl 1378.68037
Cole, Richard
122
1987
Asynchronous iterative methods for multiprocessors. Zbl 0372.68015
Baudet, Gerard M.
118
1978
Degrees of acyclicity for hypergraphs and relational database schemes. Zbl 0624.68088
Fagin, Ronald
118
1983
Tree-manipulating systems and Church-Rosser theorems. Zbl 0267.68013
Rosen, Barry K.
118
1973
A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078
Callahan, Paul B.; Kosaraju, S. Rao
116
1995
A really temporal logic. Zbl 0807.68065
Alur, Rajeev; Henzinger, Thomas A.
115
1994
Exact and approximate algorithms for scheduling nonidentical processors. Zbl 0329.68041
Horowitz, Ellis; Sahni, Sartaj
115
1976
Error analysis of direct methods of matrix inversion. Zbl 0109.09005
Wilkinson, J. H.
114
1961
Many hard examples for resolution. Zbl 0712.03008
Chvátal, Vašek; Szemerédi, Endre
113
1988
Computational limitations on learning from examples. Zbl 0662.68086
Pitt, Leonard; Valiant, Leslie G.
113
1988
Inference of reversible languages. Zbl 0485.68066
Angluin, Dana
110
1982
On finding the maxima of a set of vectors. Zbl 0316.68030
Kung, H. T.; Luccio, F.; Preparata, F. P.
109
1975
Reasoning about knowledge and probability. Zbl 0806.68098
Fagin, Ronald; Halpern, Joseph Y.
106
1994
Numerical inversion of Laplace transforms using a Fourier series approximation. Zbl 0315.65074
Crump, Kenny S.
106
1976
Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. Zbl 0165.51403
Dubner, H.; Abate, J.
105
1968
A propositional modal logic of time intervals. Zbl 0799.68175
Halpern, Joseph Y.; Shoham, Yoav
104
1991
A trade-off between space and efficiency for routing tables. Zbl 0900.68262
Peleg, David; Upfal, Eli
103
1989
A sufficient condition for backtrack-free search. Zbl 0477.68063
Freuder, Eugene C.
103
1982
On the complexity of integer programming. Zbl 0468.68050
Papadimitriou, Christos H.
103
1981
Recontamination does not help to search a graph. Zbl 0768.68048
Lapaugh, Andrea S.
101
1993
An algorithm for subgraph isomorphism. Zbl 0323.05138
Ullman, J. R.
101
1976
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088
Goemans, Michel X.; Williamson, David P.
771
1995
Color-coding. Zbl 0885.68116
Alon, Noga; Yuster, Raphael; Zwick, Uri
355
1995
Bisimulation can’t be traced. Zbl 0886.68027
Bloom, Bard; Istrail, Sorin; Meyer, Albert R.
155
1995
The complexity of probabilistic verification. Zbl 0885.68109
Courcoubetis, Costas; Yannakakis, Mihalis
129
1995
A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078
Callahan, Paul B.; Kosaraju, S. Rao
116
1995
Designing programs that check their work. Zbl 0886.68046
Blum, Manuel; Kannan, Sampath
83
1995
Sharing memory robustly in message-passing systems. Zbl 0886.68018
Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny
78
1995
Three logics for branching bisimulation. Zbl 0886.68064
de Nicola, Rocco; Vaandrager, Frits
75
1995
On the \(k\)-server conjecture. Zbl 0885.68075
Koutsoupias, Elias; Papadimitriou, Christos H.
74
1995
Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Zbl 0886.68077
Nebel, Bernhard; Bürckert, Hans-Jürgen
72
1995
The complexity of logic-based abduction. Zbl 0886.68121
Eiter, Thomas; Gottlob, Georg
66
1995
A randomized linear-time algorithm to find minimum spanning trees. Zbl 0886.68079
Karger, David R.; Klein, Philip N.; Tarjan, Robert E.
58
1995
Las Vegas algorithms for linear and integer programming when the dimension is small. Zbl 0885.65063
Clarkson, Kenneth L.
47
1995
Logical foundations of object-oriented and frame-based languages. Zbl 0885.68054
Kifer, Michael; Lausen, Georg; Wu, James
36
1995
Parametricity and local variables. Zbl 0885.68039
O’Hearn, P. W.; Tennent, R. D.
34
1995
Termination for direct sums of left-linear complete term rewriting systems. Zbl 0885.68093
Toyama, Y.; Klop, J. W.; Barendregt, H. P.
28
1995
Eigenvalues and expansion of regular graphs. Zbl 0885.68117
Kahale, Nabil
27
1995
On the minimality and global consistency of row-convex constraint networks. Zbl 0885.68087
van Beek, Peter; Dechter, Rina
25
1995
The isomorphism conjecture fails relative to a random oracle. Zbl 0886.68068
Kurtz, Stuart A.; Mahaney, Stephen R.; Royer, James S.
23
1995
On the existence of equilibria in noncooperative optimal flow control. Zbl 0885.68015
Korilis, Yannis A.; Lazar, Aurel A.
23
1995
Online tracking of mobile users. Zbl 0885.68017
Awerbuch, Baruch; Peleg, David
18
1995
NP trees and Carnap’s modal logic. Zbl 0886.68069
Gottlob, Georg
17
1995
Dynamic fault-tolerant clock synchronization. Zbl 0886.68008
Dolev, Danny; Halpern, Joseph Y.; Simons, Barbara; Strong, Ray
16
1995
On the impact of forgetting on learning machines. Zbl 0891.68088
Freivalds, Rūsiņš; Kinber, Efim; Smith, Carl H.
16
1995
A class of logic problems solvable by linear programming. Zbl 0900.03025
Conforti, Michele; Cornuéjols, Gérard
14
1995
Computing with faulty shared objects. Zbl 0890.68019
Afek, Yehuda; Greenberg, David S.; Merritt, Michael; Taubenfeld, Gadi
14
1995
Translating default logic into standard autoepistemic logic. Zbl 0884.03025
Gottlob, Georg
14
1995
Equational specifications, complete term rewriting systems, and computable and semicomputable algebras. Zbl 0885.68092
Bergstra, J. A.; Tucker, J. V.
13
1995
Subquadratic zero-knowledge. Zbl 0890.68054
Boyar, Joan; Brassard, Gilles; Peralta, René
6
1995
Provably correct theories of action. Zbl 0886.68122
Lin, Fangzhen; Shoham, Yoav
6
1995
Constructing 1-writer multireader multivalued atomic variables from regular variables. Zbl 0886.68019
Haldar, S.; Vidyasankar, K.
4
1995
Nearly optimal algorithms and bounds for multilayer channel routing. Zbl 0886.68021
Berger, Bonnie; Brady, Martin; Brown, Donna; Leighton, Tom
4
1995
Deterministic on-line routing on area-universal networks. Zbl 0885.68029
Bay, Paul; Bilardi, Gianfranco
4
1995
An optimal service policy for buffer systems. Zbl 0885.68016
Birman, Alexander; Gail, H. Richard; Hantler, Sidney L.; Rosberg, Zvi; Sidi, Moshe
4
1995
Calculating normalization constants of closed queuing networks by numerically inverting their generating functions. Zbl 0885.68026
Choudhury, Gagan L.; Leung, Kin K.; Whitt, Ward
4
1995
Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Zbl 0886.68017
Chien, Andrew A.; Kim, Jae H.
3
1995
Expected deadlock time in a multiprocessing system. Zbl 0885.68040
Compton, Kevin J.; Ravishankar, Chinya
3
1995
On the average communication complexity of asynchronous distributed algorithms. Zbl 0886.68070
Tsitsiklis, John N.; Stamoulis, George D.
2
1995
A constant-time optimal parallel string-matching algorithm. Zbl 0885.68082
Galil, Zvi
2
1995
Bounds on the speedup and efficiency of partial synchronization in parallel processing systems. Zbl 0886.68020
Chang, C. S.; Nelson, R.
1
1995
Recoverable sequence transmission protocols. Zbl 0885.68018
Tempero, Ewan D.; Ladner, Richard E.
1
1995
A theory of using history for equational systems with applications. Zbl 0885.68128
Verma, Rakesh M.
1
1995
Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067
Baker, Brenda S.
277
1994
On the hardness of approximating minimization problems. Zbl 0814.68064
Lund, Carsten; Yannakakis, Mihalis
208
1994
A really temporal logic. Zbl 0807.68065
Alur, Rajeev; Henzinger, Thomas A.
115
1994
Reasoning about knowledge and probability. Zbl 0806.68098
Fagin, Ronald; Halpern, Joseph Y.
106
1994
Cryptographic limitations on learning Boolean formulae and finite automata. Zbl 0807.68073
Kearns, Michael; Valiant, Leslie
79
1994
Biconnectivity approximations and graph carvings. Zbl 0822.68082
Khuller, Samir; Vishkin, Uzi
61
1994
On binary constraint problems. Zbl 0813.03045
Ladkin, Peter B.; Maddux, Roger D.
41
1994
Linear approximation of shortest superstrings. Zbl 0812.68075
Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis
40
1994
Counting networks. Zbl 0813.68050
Aspnes, James; Herlihy, Maurice; Shavit, Nir
34
1994
New approximation algorithms for graph coloring. Zbl 0821.68092
Blum, Avrim
28
1994
Are wait-free algorithms fast? Zbl 0812.68077
Attiya, Hagit; Lynch, Nancy; Shavit, Nir
28
1994
On the power of bounded concurrency. I: Finite automata. Zbl 0813.68138
Drusinsky, Doron; Harel, David
23
1994
Bounds on the time to reach agreement in the presence of timing uncertainty. Zbl 0807.68042
Attiya, Hagit; Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry
21
1994
Equational inference, canonical proofs, and proof orderings. Zbl 0806.68095
Bachmair, Leo; Dershowitz, Nachum
19
1994
Learning Boolean formulas. Zbl 0830.68108
Kearns, Michael; Li, Ming; Valiant, Leslie
18
1994
Instance complexity. Zbl 0807.68035
Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu
18
1994
Modular stratification and magic sets for datalog programs with negation. Zbl 0830.68028
Ross, Kenneth A.
16
1994
Shortest paths in the plane with polygonal obstacles. Zbl 0814.68129
Storer, James A.; Reif, John H.
16
1994
Probabilistic recurrence relations. Zbl 0830.68046
Karp, Richard M.
15
1994
Motion planning in the presence of moving obstacles. Zbl 0812.68115
Reif, John; Sharir, Micha
14
1994
Mixed integer programming methods for computing nonmonotonic deductive databases. Zbl 0830.68039
Bell, Colin; Nerode, Anil; Ng, Raymond T.; Subrahmanian, V. S.
13
1994
The elusive atomic register. Zbl 0806.68025
Singh, Ambuj K.; Anderson, James H.; Gouda, Mohamed G.
11
1994
Average-case analysis of algorithms for matchings and related problems. Zbl 0829.68070
Motwani, Rajeev
10
1994
Faster tree pattern matching. Zbl 0806.68055
Dubiner, Moshe; Galil, Zvi; Magen, Edith
10
1994
An analysis of ML typability. Zbl 0806.68016
Kfoury, A. J.; Tiuryn, J.; Urzyczyn, P.
10
1994
On solving equations and disequations. Zbl 0812.68064
Buntine, Wray L.; Bürckert, Hans-Jürgen
8
1994
Channel routing of multiterminal nets. Zbl 0812.68083
Gao, Shaodi; Kaufmann, Michael
8
1994
On the power of bounded concurrency. II: Pushdown automata. Zbl 0822.68067
Hirst, Tirza; Harel, David
6
1994
Diversity-based inference of finite automata. Zbl 0821.68085
Rivest, Ronald L.; Schapire, Robert E.
6
1994
Computing bounds on steady state availability of repairable computer systems. Zbl 0812.68059
Lui, John C. S.; Muntz, Richard R.
6
1994
Fishspear: A priority queue algorithm. Zbl 0807.68020
Fischer, Michael J.; Paterson, Michael S.
6
1994
Monte Carlo summation and integration applied to multiclass queuing networks. Zbl 0829.68010
Ross, Keith W.; Tsang, Danny H. K.; Wang, Jie
4
1994
The relationship between greedy parsing and symbolwise text compression. Zbl 0812.68071
Bell, Timothy C.; Witten, Ian H.
3
1994
Parallel algorithms for evaluating sequences of set-manipulation operations. Zbl 0830.68056
Atallah, Mikhail J.; Goodrich, Michael T.; Kosaraju, S. Rao
2
1994
Circumscription with homomorphisms: Solving the equality and counterexample problems. Zbl 0815.68089
Rathmann, Peter K.; Winslett, Marianne; Manasse, Mark
2
1994
Tight lower bounds for probabilistic solitude verification on anonymous rings. Zbl 0806.68038
Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David
2
1994
Parallel linear programming in fixed dimension almost surely in constant time. Zbl 0807.90080
Alon, Noga; Megiddo, Nimrod
2
1994
Efficient computation of Fourier inversion for finite groups. Zbl 0832.20027
Rockmore, Daniel N.
2
1994
Efficient decomposition methods for the analysis of multi-facility blocking models. Zbl 0812.68060
Conway, Adrian E.; Pinsky, Eugene; Tridandapani, Srinivasan
1
1994
A single-exponential upper bound for finding shortest paths in three dimensions. Zbl 0814.68079
Reif, John H.; Storer, James A.
1
1994
Optimal algorithms for parallel Givens factorization on a coarse-grained PRAM. Zbl 0802.65024
Cosnard, Michel; Daoudi, El Mostafa
1
1994
A framework for defining logics. Zbl 0778.03004
Harper, Robert; Honsell, Furio; Plotkin, Gordon
251
1993
Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006
Linial, Nathan; Mansour, Yishay; Nisan, Noam
157
1993
Atomic snapshots of shared memory. Zbl 0783.68029
Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir
134
1993
Recontamination does not help to search a graph. Zbl 0768.68048
Lapaugh, Andrea S.
101
1993
Perfectly secure message transmission. Zbl 0774.68017
Dolev, Danny; Dwork, Cynthia; Waarts, Orli; Yung, Moti
76
1993
Learning read-once formulas with queries. Zbl 0764.68139
Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek
54
1993
Complexity and algorithms for reasoning about time: A graph-theoretic approach. Zbl 0795.68095
Golumbic, Martin Charles; Shamir, Ron
48
1993
Decidability of bisimulation equivalence for processes generating context-free languages. Zbl 0801.68102
Baeten, J. C. M.; Bergstra, J. A.; Klop, J. W.
46
1993
An algebraic theory of graph reduction. Zbl 0795.68156
Arnborg, Stefan; Courcelle, Bruno; Proskurowski, Andrzej; Seese, Detlef
44
1993
Random walks on weighted graphs and applications to on-line algorithms. Zbl 0785.68071
Coppersmith, Don; Doyle, Peter; Raghavan, Prabhakar; Snir, Marc
34
1993
The minimum consistent DFA problem cannot be approximated within any polynomial. Zbl 0774.68084
Pitt, Leonard; Warmuth, Manfred K.
30
1993
Knowledge, probability, and adversaries. Zbl 0783.68120
Halpern, Joseph Y.; Tuttle, Mark R.
30
1993
Automatic recognition of tractability in inference relations. Zbl 0770.68106
McAllester, David A.
28
1993
Undecidable optimization problems for database logic programs. Zbl 0785.68021
Gaifman, Haim; Mairson, Harry; Sagiv, Yehoshua; Vardi, Moshe Y.
28
1993
Randomized parallel algorithms for backtrack search and branch-and-bound computation. Zbl 0789.68066
Karp, Richard M.; Zhang, Yanjun
22
1993
An algorithm for finding canonical sets of ground rewrite rules in polynomial time. Zbl 0779.68050
Gallier, Jean; Narendran, Paliath; Plaisted, David; Raatz, Stan; Snyder, Wayne
16
1993
Modal nonmonotonic logics: Ranges, characterization, computation. Zbl 0783.68121
Marek, V. Wiktor; Schwarz, Grigori F.; Truszczyński, Mirosław
13
1993
...and 1456 more Documents
all top 5

Cited by 34,084 Authors

120 Ibarra, Oscar H.
98 Kutrib, Martin
82 Jain, Sanjay
79 Raynal, Michel
78 Epstein, Leah
76 Saurabh, Saket
70 Otto, Friedrich
69 Rajsbaum, Sergio
68 Fomin, Fedor V.
62 Guerraoui, Rachid
58 Vardi, Moshe Ya’akov
57 Aceto, Luca
56 Cordero, Alicia
56 Stephan, Frank
56 Torregrosa Sanchez, Juan Ramón
55 Malcher, Andreas
54 Tarjan, Robert Endre
53 Sharir, Micha
53 Woeginger, Gerhard
50 Peleg, David
49 Golovach, Petr A.
49 Ingólfsdóttir, Anna
49 Schneider, Carsten
47 Halpern, Joseph Yehuda
46 Bodlaender, Hans L.
46 Inenaga, Shunsuke
46 Zehavi, Meirav
44 Wood, Derick
43 Levin, Asaf
42 Argyros, Ioannis Konstantinos
42 Book, Ronald Vernon
42 Case, John
42 Holzer, Markus
42 Okhotin, Alexander
42 Pan, Victor Yakovlevich
41 Eiter, Thomas
41 Evans, David John
41 Goldreich, Oded
41 Gottlob, Georg
40 Bergstra, Jan A.
40 Fernau, Henning
40 Iliopoulos, Costas S.
40 Pelc, Andrzej
40 Strusevich, Vitaly A.
39 Ibaraki, Toshihide
39 Lokshtanov, Daniel
39 Montanari, Angelo
39 Subramani, Krishnan
39 Taubenfeld, Gadi
38 Attiya, Hagit
38 Chen, Danny Ziyi
38 Lohrey, Markus
38 Meseguer Guaita, José
37 Engelfriet, Joost
37 Lynch, Nancy Ann
37 Wang, Haitao
36 Amir, Amihood
36 Chen, Jian-er
36 Thilikos, Dimitrios M.
35 Diaconescu, Răzvan
35 Herlihy, Maurice P.
35 Jansen, Klaus
34 Alon, Noga
34 Calude, Cristian S.
34 Chan, Timothy Moon-Yew
34 Chatterjee, Krishnendu
34 Moses, Yoram
34 Reichel, Lothar
34 Smid, Michiel H. M.
34 Soleymani, Fazlollah
34 Spirakis, Paul G.
34 Takeda, Masayuki
33 Agarwal, Pankaj Kumar
33 Behl, Ramandeep
33 Eppstein, David Arthur
33 Ésik, Zoltán
33 Fraigniaud, Pierre
33 Galil, Zvi
33 Inoue, Katsushi
33 Laporte, Gilbert
33 van Glabbeek, Robert Jan
32 Bannai, Hideo
32 Bille, Philip
32 Bozzelli, Laura
32 Crochemore, Maxime
32 Demaine, Erik D.
32 Maheshwari, Anil
32 McQuillan, Ian
32 Mehlhorn, Kurt
32 Narendran, Paliath
32 Navarro, Gonzalo
32 Papadimitriou, Christos Harilaos
32 Rozenberg, Grzegorz
32 Rytter, Wojciech
32 Salomaa, Kai T.
32 Yang, Boting
31 Allender, Eric W.
31 Bose, Prosenjit K.
31 Censor-Hillel, Keren
31 Greibach, Sheila A.
...and 33,984 more Authors
all top 5

Cited in 972 Journals

3,328 Theoretical Computer Science
1,331 Information Processing Letters
1,056 Journal of Computer and System Sciences
967 Discrete Applied Mathematics
780 European Journal of Operational Research
752 Information and Computation
713 Algorithmica
580 Artificial Intelligence
419 Computers & Operations Research
360 Acta Informatica
348 Information Sciences
291 Distributed Computing
288 International Journal of Foundations of Computer Science
285 International Journal of Computer Mathematics
280 Operations Research Letters
277 Journal of Computational and Applied Mathematics
274 Journal of Symbolic Computation
272 Mathematical Programming. Series A. Series B
271 Applied Mathematics and Computation
255 Computers & Mathematics with Applications
254 Discrete Mathematics
254 Theory of Computing Systems
246 Journal of Automated Reasoning
240 Linear Algebra and its Applications
233 Annals of Operations Research
222 Mathematical Systems Theory
220 Computing
220 Computational Geometry
214 Annals of Mathematics and Artificial Intelligence
214 Journal of Combinatorial Optimization
195 Networks
193 SIAM Journal on Computing
176 Journal of Discrete Algorithms
171 Mathematics of Computation
170 Journal of Computational Physics
163 Numerische Mathematik
155 Discrete & Computational Geometry
150 BIT
138 Real-Time Systems
133 Logical Methods in Computer Science
130 Queueing Systems
125 Annals of Pure and Applied Logic
124 Computational Complexity
120 Journal of Scheduling
117 Mathematical Structures in Computer Science
116 Formal Aspects of Computing
116 Numerical Algorithms
112 Discrete Optimization
110 The Journal of Symbolic Logic
108 Pattern Recognition
102 Theory and Practice of Logic Programming
100 Journal of Complexity
96 Fuzzy Sets and Systems
96 Journal of Logical and Algebraic Methods in Programming
95 Journal of Global Optimization
93 BIT. Nordisk Tidskrift for Informationsbehandling
91 International Journal of Computational Geometry & Applications
88 Calcolo
87 International Journal of Approximate Reasoning
86 Formal Methods in System Design
82 Journal of Optimization Theory and Applications
82 Combinatorica
80 International Journal of Computer & Information Sciences
80 Journal of Combinatorial Theory. Series B
80 Mathematical and Computer Modelling
78 Computer Physics Communications
77 The Journal of Logic and Algebraic Programming
74 RAIRO. Informatique Théorique et Applications
73 Random Structures & Algorithms
72 SIAM Journal on Discrete Mathematics
71 Journal of Cryptology
70 Journal of Soviet Mathematics
69 Computational Optimization and Applications
66 Automatica
65 Applied Numerical Mathematics
65 Machine Learning
64 Mathematical Programming
64 Naval Research Logistics
64 Journal of Applied Non-Classical Logics
64 Optimization Letters
63 Journal of Mathematical Analysis and Applications
62 Studia Logica
62 Journal of Computer Science and Technology
61 RAIRO, Informatique Théorique
60 Computer Methods in Applied Mechanics and Engineering
60 Applied Mathematical Modelling
60 Journal of Applied Logic
58 Mathematics and Computers in Simulation
58 SIAM Journal on Scientific Computing
57 Cybernetics
57 INFORMS Journal on Computing
56 European Journal of Combinatorics
56 Cybernetics and Systems Analysis
56 International Transactions in Operational Research
55 International Journal for Numerical Methods in Engineering
55 Kybernetika
55 Journal of Functional Programming
53 International Journal of Production Research
53 Journal of Parallel and Distributed Computing
53 ACM Transactions on Computational Logic
...and 872 more Journals
all top 5

Cited in 62 Fields

22,724 Computer science (68-XX)
6,551 Operations research, mathematical programming (90-XX)
4,233 Combinatorics (05-XX)
3,697 Numerical analysis (65-XX)
3,659 Mathematical logic and foundations (03-XX)
1,527 Information and communication theory, circuits (94-XX)
954 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
918 Probability theory and stochastic processes (60-XX)
528 Linear and multilinear algebra; matrix theory (15-XX)
527 Statistics (62-XX)
495 Number theory (11-XX)
439 Biology and other natural sciences (92-XX)
426 Convex and discrete geometry (52-XX)
417 Systems theory; control (93-XX)
364 Group theory and generalizations (20-XX)
308 Order, lattices, ordered algebraic structures (06-XX)
287 Quantum theory (81-XX)
279 Partial differential equations (35-XX)
244 Ordinary differential equations (34-XX)
241 Field theory and polynomials (12-XX)
233 Approximations and expansions (41-XX)
223 Fluid mechanics (76-XX)
201 Category theory; homological algebra (18-XX)
200 Mechanics of deformable solids (74-XX)
185 Commutative algebra (13-XX)
167 Calculus of variations and optimal control; optimization (49-XX)
164 General algebraic systems (08-XX)
150 Algebraic geometry (14-XX)
134 Statistical mechanics, structure of matter (82-XX)
133 Dynamical systems and ergodic theory (37-XX)
124 Integral equations (45-XX)
114 Operator theory (47-XX)
113 Special functions (33-XX)
95 Integral transforms, operational calculus (44-XX)
94 Real functions (26-XX)
91 History and biography (01-XX)
91 Functions of a complex variable (30-XX)
80 Geometry (51-XX)
78 Harmonic analysis on Euclidean spaces (42-XX)
71 Associative rings and algebras (16-XX)
70 General topology (54-XX)
54 General and overarching topics; collections (00-XX)
50 Manifolds and cell complexes (57-XX)
50 Mechanics of particles and systems (70-XX)
49 Difference and functional equations (39-XX)
45 Functional analysis (46-XX)
45 Optics, electromagnetic theory (78-XX)
43 Algebraic topology (55-XX)
39 Classical thermodynamics, heat transfer (80-XX)
37 Geophysics (86-XX)
27 Measure and integration (28-XX)
23 Nonassociative rings and algebras (17-XX)
22 Differential geometry (53-XX)
16 Global analysis, analysis on manifolds (58-XX)
11 Topological groups, Lie groups (22-XX)
10 Sequences, series, summability (40-XX)
10 Relativity and gravitational theory (83-XX)
7 Potential theory (31-XX)
7 Several complex variables and analytic spaces (32-XX)
7 Mathematics education (97-XX)
5 Abstract harmonic analysis (43-XX)
1 Astronomy and astrophysics (85-XX)

Citations by Year