Edit Profile (opens in new tab) Galil, Zvi Co-Author Distance Author ID: galil.zvi Published as: Galil, Zvi; Galil, Z. Homepage: http://www1.cs.columbia.edu/~galil/ External Links: MGP · Wikidata · dblp · IdRef Documents Indexed: 152 Publications since 1974 5 Contributions as Editor Co-Authors: 66 Co-Authors with 128 Joint Publications 3,345 Co-Co-Authors all top 5 Co-Authors 29 single-authored 14 Italiano, Giuseppe Francesco 12 Giancarlo, Raffaele 12 Park, Kunsoo 11 Ďuriš, Pavol 11 Eppstein, David Arthur 11 Kiefer, Jack Carl 10 Breslauer, Dany 8 Apostolico, Alberto 8 Yung, Moti 7 Ben-Amram, Amir M. 7 Margalit, Oded 5 Seiferas, Joel I. 4 Alon, Noga 4 Crochemore, Maxime 4 Megiddo, Nimrod 4 Spencer, Thomas H. 3 Averbuch, Amir Z. 3 Winograd, Shmuel 2 Gabow, Harold N. 2 Gąsieniec, Leszek Antoni 2 Haber, Stuart 2 Kannan, Ravindran 2 Landau, Gad M. 2 Manber, Udi 2 Mehlhorn, Kurt 2 Muthukrishnan, S. Muthu 2 Nissenzweig, Amnon 2 Pan, Victor Yakovlevich 2 Paul, Wolfgang Jakob 2 Szemerédi, Endre 1 Amir, Amihood 1 Chaimovich, Mark 1 Cole, Richard John 1 Czumaj, Artur 1 Dubiner, Moshe 1 Farach-Colton, Martin 1 Farach, Martin 1 Franklin, Matthew K. 1 Freiman, Gregory A. 1 Gabber, Ofer 1 Greenberg, Albert G. 1 Hariharan, Ramesh 1 Ladner, Richard E. 1 Leven, Daniel 1 Magen, Edith 1 Mayer, Alain 1 Micali, Silvio 1 Milman, Vitali D. 1 Naamad, Amnon 1 Naor, Moni 1 Park, Jong Geun 1 Paterson, Mike S. 1 Plandowski, Wojciech 1 Rabani, Yuval 1 Reischuk, Rüdiger 1 Rosenberg, Arnold Leonard 1 Rytter, Wojciech 1 Sarnak, Neil 1 Schieber, Baruch 1 Schnitger, Georg 1 Simon, Janos 1 Tardos, Éva 1 Tarjan, Robert Endre 1 Ukkonen, Esko 1 Wood, Derick 1 Yu, Xiangdong all top 5 Serials 18 SIAM Journal on Computing 13 Theoretical Computer Science 12 Journal of Computer and System Sciences 11 Journal of the Association for Computing Machinery 6 Information Processing Letters 5 Information and Computation 4 Information and Control 4 Journal of Statistical Planning and Inference 4 Mathematical Systems Theory 4 Journal of Complexity 3 Acta Informatica 3 Technometrics 3 Combinatorica 3 Algorithmica 3 Journal of the ACM 3 Lecture Notes in Computer Science 2 The Annals of Statistics 2 Journal of Algorithms 1 Discrete Applied Mathematics 1 Computing 1 International Journal of Game Theory 1 Mathematics of Operations Research 1 SIAM Journal on Discrete Mathematics 1 Journal of Parallel and Distributed Computing 1 Communications of the ACM 1 Computing Surveys 1 NATO ASI Series. Series F. Computer and Systems Sciences 1 ACM Transactions on Algorithms all top 5 Fields 133 Computer science (68-XX) 19 Combinatorics (05-XX) 18 Operations research, mathematical programming (90-XX) 12 Statistics (62-XX) 11 Numerical analysis (65-XX) 10 Mathematical logic and foundations (03-XX) 9 Information and communication theory, circuits (94-XX) 5 General and overarching topics; collections (00-XX) 3 Biology and other natural sciences (92-XX) 2 Number theory (11-XX) 2 Field theory and polynomials (12-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 139 Publications have been cited 1,834 times in 1,434 Documents Cited by ▼ Year ▼ Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Zbl 0608.05027 Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. 102 1986 NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037 Leven, Daniel; Galil, Zvi 89 1983 Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045 Gabber, Ofer; Galil, Zvi 83 1981 D-optimum weighing designs. Zbl 0466.62066 Galil, Z.; Kiefer, J. 55 1980 Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon 52 1997 Time-space-optimal string matching. Zbl 0509.68101 Galil, Zvi; Seiferas, Joel 49 1983 Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064 Galil, Zvi 40 1986 An improved algorithm for approximate string matching. Zbl 0711.68048 Galil, Zvi; Park, Kunsoo 34 1990 Construction methods for D-optimum weighing designs when n=3(mod 4). Zbl 0489.62068 Galil, Z.; Kiefer, J. 33 1982 On the exponent of all pairs shortest path problem. Zbl 0877.68090 Alon, Noga; Galil, Zvi; Margalit, Oded 32 1997 On the complexity of regular resolution and the Davis-Putnam procedure. Zbl 0385.68048 Galil, Zvi 31 1977 Data structures and algorithms for approximate string matching. Zbl 0646.68078 Galil, Z.; Giancarlo, R. 31 1988 Pattern matching algorithms. Zbl 0874.68006 28 1997 Sparsification – a technique for speeding up dynamic graph algorithms. (Extended abstract). Zbl 0977.68560 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon 26 1992 Comparison of rotatable designs for regression on balls. I. (quadratic). Zbl 0394.62058 Galil, Z.; Kiefer, J. 26 1977 Comparison of simplex designs for quadratic mixture models. Zbl 0372.62058 Galil, Z.; Kiefer, J. 25 1977 Optimal parallel algorithms for string matching. Zbl 0588.68022 Galil, Zvi 25 1985 An almost linear-time algorithm for computing a dependency basis in a relational database. Zbl 0485.68090 Galil, Zvi 24 1982 Parallel detection of all palindromes in a string. Zbl 0873.68039 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 24 1995 Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 23 1992 On O(EV log V) algorithm for finding a maximal weighted matching in general graphs. Zbl 0589.68050 Galil, Zvi; Micali, Silvio; Gabow, Harold 22 1986 Better expanders and superconcentrators. Zbl 0641.68102 Alon, N.; Galil, Z.; Milman, V. D. 22 1987 Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707 Galil, Zvi; Park, Kunsoo 21 1992 Cyclic ordering is NP-complete. Zbl 0383.68045 Galil, Zvi; Megiddo, Nimrod 20 1978 A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032 Galil, Zvi; Park, Kunsoo 20 1990 Hierarchies of complete problems. Zbl 0304.68044 Galil, Zvi 19 1976 Dynamic dictionary matching. Zbl 0942.68783 Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo 19 1994 On improving the worst case running time of the Boyer-Moore string matching algorithm. Zbl 0413.68041 Galil, Zvi 18 1979 Finding the vertex connectivity of graphs. Zbl 0446.68053 Galil, Zvi 18 1980 Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562 Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni 18 1992 Monotone switching circuits and Boolean matrix product. Zbl 0323.94019 Mehlhorn, K.; Galil, Z. 18 1976 Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090 Galil, Zvi; Giancarlo, Raffaele 18 1989 All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081 Galil, Zvi; Margalit, Oded 18 1997 Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053 Breslauer, D.; Galil, Z. 18 1995 Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658 Galil, Zvi; Mayer, Alain; Yung, Moti 17 1995 A linear-time on-line recognition algorithm for ”palstar”. Zbl 0365.68058 Galil, Zvi; Seiferas, Joel 17 1978 Comparison of design for quadratic regression of cubes. Zbl 0381.62062 Galil, Z.; Kiefer, J. 17 1977 Separator based sparsification for dynamic planar graph algorithms. Zbl 1310.05197 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 17 1993 Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. Zbl 1133.68469 Franklin, Matthew; Galil, Zvi; Yung, Moti 17 2000 A fast selection algorithm and the problem of optimum distribution of effort. Zbl 0404.90062 Galil, Zvi; Megiddo, Nimrod 16 1979 An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057 Breslauer, Dany; Galil, Zvi 16 1990 On finding most uniform spanning trees. Zbl 0645.05035 Galil, Zvi; Schieber, Baruch 16 1988 Fooling a two way automaton or one pushdown store is better than one counter for two way machines. Zbl 0486.68084 Duris, Pavol; Galil, Zvi 16 1982 String matching in real time. Zbl 0454.68009 Galil, Zvi 15 1981 Lower bounds on communication complexity. Zbl 0635.68034 Duris, Pavol; Galil, Zvi; Schnitger, Georg 15 1987 An \(O(EV\log^2V)\) algorithm for the maximal flow problem. Zbl 0449.90094 Galil, Zvi; Naamad, Amnon 14 1980 Time- and space-saving computer methods, related to Mitchell’s DETMAX, for finding D-optimum designs. Zbl 0459.62060 Galil, Z.; Kiefer, J. 14 1980 Improved processor bounds for combinatorial problems in RNC. Zbl 0685.68048 Galil, Z.; Pan, V. 14 1988 Extrapolation designs and \(\Phi_p\)-optimum designs for cubic regression on the \(q\)-ball. Zbl 0412.62055 Galil, Z.; Kiefer, J. 13 1979 Alphabet-independent two-dimensional witness computation. Zbl 0861.68032 Galil, Zvi; Park, Kunsoo 13 1996 Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 13 1996 A lower bound for parallel string matching. Zbl 0756.68048 Breslauer, Dany; Galil, Zvi 13 1992 Real-time streaming string-matching. Zbl 1339.68324 Breslauer, Dany; Galil, Zvi 13 2011 Some open problems in the theory of computation as questions about two- way deterministic pushdown automaton languages. Zbl 0356.68064 Galil, Zvi 12 1977 Optimum weighing designs. Zbl 0462.62059 Kiefer, J.; Galil, Z. 11 1980 Improved string matching with k mismatches. Zbl 0608.68058 Galil, Zvi; Giancarlo, Raffaele 11 1985 Sparse dynamic programming. II: Convex and concave cost functions. Zbl 0816.90130 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 11 1992 On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store. Zbl 0523.68037 Duris, Pavol; Galil, Zvi 11 1982 A time-space tradeoff for language recognition. Zbl 0533.68047 Dúriś, Pavol; Galil, Zvi 11 1984 Saving space in fast string-matching. Zbl 0446.68041 Galil, Zvi; Seiferas, Joel 10 1980 Open problems in stringology. Zbl 0607.68054 Galil, Zvi 10 1985 An O(n \(2(m+n\,\log \,n)\log \,n)\) min-cost flow algorithm. Zbl 0652.90039 Galil, Zvi; Tardos, Éva 10 1988 Faster tree pattern matching. Zbl 0806.68055 Dubiner, Moshe; Galil, Zvi; Magen, Edith 10 1994 Real-time algorithms for string-matching and palindrome recognition. Zbl 0365.68032 Galil, Zvi 9 1976 Palindrome recognition in real time by a multitape Turing machine. Zbl 0386.03020 Galil, Zvi 9 1978 Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088 Galil, Zvi; Park, Kunsoo 9 1992 On the exact complexity of string matching: Upper bounds. Zbl 0761.68046 Galil, Zvi; Giancarlo, Raffaele 9 1992 All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089 Galil, Zvi; Margalit, Oded 9 1997 An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem. Zbl 0456.68044 Galil, Zvi 8 1980 Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Zbl 0328.68047 Galil, Zvi 8 1976 Combinatorial algorithms on words. (Proceedings of the NATO Advanced Research Workshop on Combinatorial Algorithms on Words held at Maratea, Italy, June 18-22, 1984). Zbl 0564.00027 8 1985 Real-time streaming string-matching. Zbl 1398.68701 Breslauer, Dany; Galil, Zvi 8 2014 Parallel string matching with k mismatches. Zbl 0636.68084 Galil, Zvi; Giancarlo, Raffaele 8 1987 On pointers versus addresses. Zbl 0799.68114 Ben-Amram, Amir M.; Galil, Zvi 8 1992 Fully dynamic planarity testing with applications. Zbl 1064.05502 Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil 8 1999 An almost linear-time algorithm for the dense subset-sum problem. Zbl 0736.68041 Galil, Zvi; Margalit, Oded 8 1991 Optimal parallel algorithms for periods, palindromes and squares (extended abstract). Zbl 1425.68466 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 8 1992 Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040 Galil, Zvi; Pan, Victor 7 1989 Sparse dynamic programming. Zbl 0785.90094 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 7 1990 Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 7 1998 Efficient parallel algorithms for linear recurrence computation. Zbl 0487.68028 Greenberg, Albert C.; Ladner, Richard E.; Paterson, Michael S.; Galil, Zvi 7 1982 Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557 Galil, Zvi; Yu, Xiangdong 6 1995 On resolution with clauses of bounded size. Zbl 0368.68085 Galil, Zvi 6 1977 Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030 Chaimovich, Mark; Freiman, Gregory; Galil, Zvi 6 1989 Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency. Zbl 0820.90122 Galil, Zvi; Park, Kunsoo 6 1994 An efficient general-purpose parallel computer. Zbl 0515.68022 Galil, Zvi; Paul, Wolfgang J. 6 1983 On the exact complexity of string matching: Lower bounds. Zbl 0738.68042 Galil, Zvi; Giancarlo, Raffaele 6 1991 On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines. Zbl 0676.68019 Galil, Zvi; Kannan, Ravi; Szemerédi, Endre 6 1989 Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117 Galil, Zvi; Italiano, Giuseppe F. 6 1991 Real-time recognition of substring repetition and reversal. Zbl 0349.68035 Seiferas, Joel; Galil, Zvi 5 1977 Comparison of Box-Draper and d-optimum designs for experiments with mixtures. Zbl 0369.62087 Galil, Z.; Kiefer, J. 5 1977 Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053 Galil, Zvi; Margalit, Olded 5 1993 Two tapes are better than one for nondeterministic machines. Zbl 0558.68045 Dúriś, Pavol; Galil, Zvi 5 1984 Comparison of designs equivalent under one or two criteria. Zbl 0533.62063 Galil, Z.; Kiefer, J. 5 1983 Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007 Galil, Zvi; Haber, Stuart; Yung, Moti 5 1989 Fully dynamic algorithms for 2-edge connectivity. Zbl 0760.68022 Galil, Zvi; Italiano, Giuseppe F. 5 1992 Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080 Galil, Zvi; Italiano, Giuseppe F. 5 1993 Applications of efficient mergeable heaps for optimization problems on trees. Zbl 0431.68062 Galil, Zvi 4 1980 Linear-time string-matching using only a fixed number of local storage locations. Zbl 0454.68008 Galil, Zvi; Seiferas, Joel 4 1981 Parallel detection of all palindromes in a string. Zbl 0941.68825 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 4 1994 Real-time streaming string-matching. Zbl 1398.68701 Breslauer, Dany; Galil, Zvi 8 2014 Forty years of text indexing. Zbl 1381.68067 Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S. 4 2013 Real-time streaming string-matching. Zbl 1339.68324 Breslauer, Dany; Galil, Zvi 13 2011 Three-dimensional periodicity and its application to pattern matching. Zbl 1087.68080 Galil, Zvi; Park, Jong Geun; Park, Kunsoo 1 2004 Lower bounds for dynamic data structures on algebraic RAMs. Zbl 1050.68025 Ben-Amram, A. M.; Galil, Z. 1 2002 A generalization of a lower bound technique due to Fredman and Saks. Zbl 0992.68034 Ben-Amram, A. M.; Galil, Z. 1 2001 Topological lower bounds on algebraic random access machines. Zbl 1017.68057 Ben-Amram, Amir M.; Galil, Zvi 1 2001 Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. Zbl 1133.68469 Franklin, Matthew; Galil, Zvi; Yung, Moti 17 2000 Fully dynamic planarity testing with applications. Zbl 1064.05502 Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil 8 1999 Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 7 1998 Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon 52 1997 On the exponent of all pairs shortest path problem. Zbl 0877.68090 Alon, Noga; Galil, Zvi; Margalit, Oded 32 1997 Pattern matching algorithms. Zbl 0874.68006 28 1997 All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081 Galil, Zvi; Margalit, Oded 18 1997 All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089 Galil, Zvi; Margalit, Oded 9 1997 Constant-time randomized parallel string matching. Zbl 0885.68078 Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech 4 1997 Alphabet-independent two-dimensional witness computation. Zbl 0861.68032 Galil, Zvi; Park, Kunsoo 13 1996 Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 13 1996 Parallel detection of all palindromes in a string. Zbl 0873.68039 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 24 1995 Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053 Breslauer, D.; Galil, Z. 18 1995 Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658 Galil, Zvi; Mayer, Alain; Yung, Moti 17 1995 Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557 Galil, Zvi; Yu, Xiangdong 6 1995 On the power of the shift instruction. Zbl 0828.68074 Ben-Amram, Amir M.; Galil, Zvi 4 1995 Work-time-optimal parallel algorithms for string problems. (Extended abstract). Zbl 0978.68531 Czumaj, Artur; Galil, Zvi; Gąsieniec, Leszek; Park, Kunsoo; Plandowski, Wojciech 3 1995 A constant-time optimal parallel string-matching algorithm. Zbl 0885.68082 Galil, Zvi 2 1995 Sensing versus nonsensing automata. Zbl 1412.68127 Ďuriš, Pavol; Galil, Zvi 1 1995 Dynamic dictionary matching. Zbl 0942.68783 Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo 19 1994 Faster tree pattern matching. Zbl 0806.68055 Dubiner, Moshe; Galil, Zvi; Magen, Edith 10 1994 Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency. Zbl 0820.90122 Galil, Zvi; Park, Kunsoo 6 1994 Parallel detection of all palindromes in a string. Zbl 0941.68825 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 4 1994 Separator based sparsification for dynamic planar graph algorithms. Zbl 1310.05197 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. 17 1993 Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053 Galil, Zvi; Margalit, Olded 5 1993 Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080 Galil, Zvi; Italiano, Giuseppe F. 5 1993 Efficient comparison based string matching. Zbl 0783.68052 Breslauer, Dany; Galil, Zvi 3 1993 On the power of multiple reads in a chip. Zbl 0783.68061 Ďuriš, Pavol; Galil, Zvi 1 1993 Sparsification – a technique for speeding up dynamic graph algorithms. (Extended abstract). Zbl 0977.68560 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon 26 1992 Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 23 1992 Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707 Galil, Zvi; Park, Kunsoo 21 1992 Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562 Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni 18 1992 A lower bound for parallel string matching. Zbl 0756.68048 Breslauer, Dany; Galil, Zvi 13 1992 Sparse dynamic programming. II: Convex and concave cost functions. Zbl 0816.90130 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 11 1992 Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088 Galil, Zvi; Park, Kunsoo 9 1992 On the exact complexity of string matching: Upper bounds. Zbl 0761.68046 Galil, Zvi; Giancarlo, Raffaele 9 1992 On pointers versus addresses. Zbl 0799.68114 Ben-Amram, Amir M.; Galil, Zvi 8 1992 Optimal parallel algorithms for periods, palindromes and squares (extended abstract). Zbl 1425.68466 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi 8 1992 Fully dynamic algorithms for 2-edge connectivity. Zbl 0760.68022 Galil, Zvi; Italiano, Giuseppe F. 5 1992 On the space complexity of some algorithms for sequence comparison. Zbl 0745.68060 Rabani, Yuval; Galil, Zvi 1 1992 An almost linear-time algorithm for the dense subset-sum problem. Zbl 0736.68041 Galil, Zvi; Margalit, Oded 8 1991 On the exact complexity of string matching: Lower bounds. Zbl 0738.68042 Galil, Zvi; Giancarlo, Raffaele 6 1991 Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117 Galil, Zvi; Italiano, Giuseppe F. 6 1991 A note on set union with arbitrary deunions. Zbl 0714.68039 Galil, Zvi; Italiano, Giuseppe F. 3 1991 Two lower bounds in asynchronous distributed computation. Zbl 0731.68043 Duris, Pavol; Galil, Zvi 3 1991 An almost linear-time algorithm for the dense subset-sum problem. Zbl 0769.68043 Galil, Zvi; Margalit, Oded 2 1991 Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u]/\langle{} u^ n \rangle\). Zbl 0744.68071 Averbuch, Amir; Galil, Zvi; Winograd, Shmuel 1 1991 An improved algorithm for approximate string matching. Zbl 0711.68048 Galil, Zvi; Park, Kunsoo 34 1990 A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032 Galil, Zvi; Park, Kunsoo 20 1990 An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057 Breslauer, Dany; Galil, Zvi 16 1990 Sparse dynamic programming. Zbl 0785.90094 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. 7 1990 Efficient algorithms with applications to molecular biology. Zbl 0687.68024 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele 1 1990 Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090 Galil, Zvi; Giancarlo, Raffaele 18 1989 Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040 Galil, Zvi; Pan, Victor 7 1989 Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030 Chaimovich, Mark; Freiman, Gregory; Galil, Zvi 6 1989 On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines. Zbl 0676.68019 Galil, Zvi; Kannan, Ravi; Szemerédi, Endre 6 1989 Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007 Galil, Zvi; Haber, Stuart; Yung, Moti 5 1989 An improved algorithm for approximate string matching. Zbl 0683.68034 Galil, Zvi; Park, Kunsoo 4 1989 On 3-pushdown graphs with large separators. Zbl 0726.05042 Galil, Z.; Kannan, R.; Szemerédi, E. 4 1989 Parallel algorithmic techniques for combinatorial computation. Zbl 0691.68037 Eppstein, David; Galil, Zvi 3 1989 Data structures and algorithms for approximate string matching. Zbl 0646.68078 Galil, Z.; Giancarlo, R. 31 1988 On finding most uniform spanning trees. Zbl 0645.05035 Galil, Zvi; Schieber, Baruch 16 1988 Improved processor bounds for combinatorial problems in RNC. Zbl 0685.68048 Galil, Z.; Pan, V. 14 1988 An O(n \(2(m+n\,\log \,n)\log \,n)\) min-cost flow algorithm. Zbl 0652.90039 Galil, Zvi; Tardos, Éva 10 1988 Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u]/<Q(u)^{\ell}>\), \(\ell >1\). Zbl 0656.68040 Averbuch, Amir; Galil, Zvi; Winograd, Shmuel 4 1988 Better expanders and superconcentrators. Zbl 0641.68102 Alon, N.; Galil, Z.; Milman, V. D. 22 1987 Lower bounds on communication complexity. Zbl 0635.68034 Duris, Pavol; Galil, Zvi; Schnitger, Georg 15 1987 Parallel string matching with k mismatches. Zbl 0636.68084 Galil, Zvi; Giancarlo, Raffaele 8 1987 Partitioned encryption and achieving simultaneity by partitioning. Zbl 0637.94015 Galil, Zvi; Yung, Moti 3 1987 Distributed algorithms in synchronous broadcasting networks. Zbl 0612.68007 Galil, Zvi; Landau, Gad M.; Yung, Mordechai M. 2 1987 Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Zbl 0608.05027 Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. 102 1986 Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064 Galil, Zvi 40 1986 On O(EV log V) algorithm for finding a maximal weighted matching in general graphs. Zbl 0589.68050 Galil, Zvi; Micali, Silvio; Gabow, Harold 22 1986 Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. Zbl 0636.68035 Averbuch, Amir; Winograd, Shmuel; Galil, Zvi 4 1986 Optimal parallel algorithms for string matching. Zbl 0588.68022 Galil, Zvi 25 1985 Improved string matching with k mismatches. Zbl 0608.68058 Galil, Zvi; Giancarlo, Raffaele 11 1985 Open problems in stringology. Zbl 0607.68054 Galil, Zvi 10 1985 Combinatorial algorithms on words. (Proceedings of the NATO Advanced Research Workshop on Combinatorial Algorithms on Words held at Maratea, Italy, June 18-22, 1984). Zbl 0564.00027 8 1985 Computing \(D\)-optimum weighing designs: where statistics combinatorics, and computation meet. Zbl 1373.62397 Galil, Zvi 3 1985 A time-space tradeoff for language recognition. Zbl 0533.68047 Dúriś, Pavol; Galil, Zvi 11 1984 Two tapes are better than one for nondeterministic machines. Zbl 0558.68045 Dúriś, Pavol; Galil, Zvi 5 1984 Two nonlinear lower bounds for on-line computations. Zbl 0589.68039 Ďuriš, Pavol; Galil, Zvi; Paul, Wolfgang; Reischuk, Ruediger 4 1984 NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037 Leven, Daniel; Galil, Zvi 89 1983 Time-space-optimal string matching. Zbl 0509.68101 Galil, Zvi; Seiferas, Joel 49 1983 An efficient general-purpose parallel computer. Zbl 0515.68022 Galil, Zvi; Paul, Wolfgang J. 6 1983 Comparison of designs equivalent under one or two criteria. Zbl 0533.62063 Galil, Z.; Kiefer, J. 5 1983 Construction methods for D-optimum weighing designs when n=3(mod 4). Zbl 0489.62068 Galil, Z.; Kiefer, J. 33 1982 An almost linear-time algorithm for computing a dependency basis in a relational database. Zbl 0485.68090 Galil, Zvi 24 1982 Fooling a two way automaton or one pushdown store is better than one counter for two way machines. Zbl 0486.68084 Duris, Pavol; Galil, Zvi 16 1982 On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store. Zbl 0523.68037 Duris, Pavol; Galil, Zvi 11 1982 Efficient parallel algorithms for linear recurrence computation. Zbl 0487.68028 Greenberg, Albert C.; Ladner, Richard E.; Paterson, Michael S.; Galil, Zvi 7 1982 On the characterization of D-optimum weighing designs for n\(\equiv 3(mod\,4)\). Zbl 0598.62087 Galil, Z.; Kiefer, J. 4 1982 On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store. Zbl 0485.68079 Duris, Pavol; Galil, Zvi 1 1982 ...and 39 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 2,067 Authors 30 Galil, Zvi 24 Crochemore, Maxime 24 Rytter, Wojciech 22 Amir, Amihood 19 Apostolico, Alberto 17 Iliopoulos, Costas S. 16 Lingas, Andrzej 16 Park, Kunsoo 14 Link, Sebastian 13 Breslauer, Dany 13 Paulusma, Daniël 13 Radoszewski, Jakub 13 Rauch Henzinger, Monika 12 Gąsieniec, Leszek Antoni 12 Inenaga, Shunsuke 12 Landau, Gad M. 11 Eppstein, David Arthur 11 Mandal, Nripes Kumar 10 Alon, Noga 10 Charalampopoulos, Panagiotis 10 Gawrychowski, Paweł 10 Grossi, Roberto 10 Kowalski, Dariusz R. 10 Pissis, Solon P. 10 Porat, Ely 10 Punnen, Abraham P. 10 Schwarzmann, Alexander A. 9 de Figueiredo, Celina M. Herrera 9 Kolpakov, Roman M. 9 Pal, Manisha 9 Pan, Victor Yakovlevich 9 Tarjan, Robert Endre 8 Hromkovič, Juraj 8 Kociumaka, Tomasz 8 Kounias, Stratis 8 Mignosi, Filippo 8 Starikovskaya, Tatiana A. 8 Takaoka, Tadao 8 Takeda, Masayuki 7 Bannai, Hideo 7 Fernández-Baca, David 7 Italiano, Giuseppe Francesco 7 Kucherov, Gregory 7 Lecroq, Thierry 7 Navarro, Gonzalo 7 Shur, Arseny M. 7 Ukkonen, Esko 7 Vishkin, Uzi 7 Wigderson, Avi 7 Wong, Chi Song 6 Baeza-Yates, Ricardo A. 6 Baswana, Surender 6 Bille, Philip 6 Chlebus, Bogdan Stanislaw 6 Giancarlo, Raffaele 6 Golovach, Petr A. 6 Heiligers, Berthold 6 Huda, Shahariar 6 Kiefer, Jack Carl 6 Levy, Avivit 6 Pukelsheim, Friedrich 6 Shinohara, Ayumi 5 Afraimovich, L. G. 5 Brimkov, Valentin E. 5 Butman, Ayelet 5 Chudnovsky, Maria 5 Czumaj, Artur 5 Dehghan, Ali A. 5 Draper, Norman R. 5 Drezner, Zvi 5 Ďuriš, Pavol 5 Georgiou, Chryssis 5 Goldreich, Oded 5 Hartmann, Sven 5 Luccio, Fabrizio 5 Masaro, Joseph C. 5 Neubauer, Michael G. 5 Schaudt, Oliver 5 Seiferas, Joel I. 5 Urquhart, Alasdair 5 Vildhøj, Hjalte Wedel 5 Waleń, Tomasz 5 Wegener, Ingo 5 Zhong, Mingxian 4 Alzamel, Mai 4 Blanchet-Sadri, Francine 4 Brimberg, Jack 4 Bringmann, Karl 4 Chadjiconstantinidis, Stathis 4 Chao, Kunmao 4 Chrobak, Marek 4 Duan, Ran 4 Epifanio, Chiara 4 Fomin, Fedor V. 4 Gørtz, Inge Li 4 Holzer, Markus 4 Ibarra, Oscar H. 4 Klimošová, Tereza 4 Kratsch, Dieter 4 Lewenstein, Moshe ...and 1,967 more Authors all top 5 Cited in 211 Serials 204 Theoretical Computer Science 95 Information Processing Letters 92 Algorithmica 66 Discrete Applied Mathematics 56 Journal of Computer and System Sciences 41 Journal of Statistical Planning and Inference 37 Information and Computation 27 Journal of Discrete Algorithms 20 European Journal of Operational Research 19 Discrete Mathematics 19 Communications in Statistics. Theory and Methods 15 SIAM Journal on Computing 14 Statistics & Probability Letters 14 Combinatorica 14 International Journal of Foundations of Computer Science 13 International Journal of Computer Mathematics 13 Linear Algebra and its Applications 13 Computational Complexity 12 Distributed Computing 12 Theory of Computing Systems 12 Journal of Combinatorial Optimization 11 Operations Research Letters 10 Acta Informatica 9 Artificial Intelligence 8 Mathematical Systems Theory 8 Journal of Complexity 7 Information Sciences 7 Journal of Combinatorial Theory. Series B 7 Networks 7 European Journal of Combinatorics 7 SIAM Journal on Algebraic and Discrete Methods 7 Mathematical Programming. Series A. Series B 7 Annals of Mathematics and Artificial Intelligence 6 Computers & Mathematics with Applications 6 Computers & Operations Research 6 Annals of Operations Research 6 Computational Statistics and Data Analysis 6 Parallel Algorithms and Applications 5 Computing 5 Automation and Remote Control 4 Metrika 4 International Journal of Game Theory 4 Journal of Combinatorial Theory. Series A 4 Kybernetika 4 Journal of Parallel and Distributed Computing 4 Random Structures & Algorithms 4 Japan Journal of Industrial and Applied Mathematics 4 RAIRO. Informatique Théorique et Applications 4 Combinatorics, Probability and Computing 4 Journal of Mathematical Sciences (New York) 4 Algorithms 3 The Canadian Journal of Statistics 3 Linear and Multilinear Algebra 3 The Annals of Statistics 3 Applied Mathematics and Computation 3 BIT 3 Transactions of the American Mathematical Society 3 Annals of Pure and Applied Logic 3 Discrete & Computational Geometry 3 Journal of Automated Reasoning 3 International Journal of Computational Geometry & Applications 3 Communications in Statistics. Simulation and Computation 3 The Electronic Journal of Combinatorics 3 INFORMS Journal on Computing 3 Journal of Applied Mathematics and Computing 3 ACM Transactions on Computational Logic 3 Mathematics in Computer Science 3 ACM Transactions on Algorithms 3 Computer Science Review 2 Journal of Mathematical Analysis and Applications 2 Physica A 2 Journal of Graph Theory 2 Journal of Soviet Mathematics 2 Naval Research Logistics 2 Statistics 2 Journal of Symbolic Computation 2 Applied Mathematics Letters 2 SIAM Journal on Discrete Mathematics 2 Journal of Cryptology 2 Formal Aspects of Computing 2 Journal of Global Optimization 2 Pattern Recognition 2 SIAM Review 2 Cybernetics and Systems Analysis 2 Journal of Computer and Systems Sciences International 2 SIAM Journal on Scientific Computing 2 Finite Fields and their Applications 2 Journal of Heuristics 2 Optimization Methods & Software 2 Mathematical Methods of Operations Research 2 Journal of Discrete Mathematical Sciences & Cryptography 2 RAIRO. Theoretical Informatics and Applications 2 Discrete Optimization 2 Logical Methods in Computer Science 2 Nonlinear Analysis. Hybrid Systems 2 The Annals of Applied Statistics 2 Theory of Computing 1 Indian Journal of Pure & Applied Mathematics 1 Israel Journal of Mathematics 1 Journal of Statistical Physics ...and 111 more Serials all top 5 Cited in 42 Fields 1,027 Computer science (68-XX) 391 Combinatorics (05-XX) 202 Operations research, mathematical programming (90-XX) 134 Statistics (62-XX) 63 Mathematical logic and foundations (03-XX) 60 Information and communication theory, circuits (94-XX) 41 Numerical analysis (65-XX) 38 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 38 Biology and other natural sciences (92-XX) 24 Linear and multilinear algebra; matrix theory (15-XX) 12 Number theory (11-XX) 12 Probability theory and stochastic processes (60-XX) 8 Order, lattices, ordered algebraic structures (06-XX) 8 Field theory and polynomials (12-XX) 8 Group theory and generalizations (20-XX) 8 Convex and discrete geometry (52-XX) 7 Systems theory; control (93-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 4 Geometry (51-XX) 4 Manifolds and cell complexes (57-XX) 4 Statistical mechanics, structure of matter (82-XX) 3 General and overarching topics; collections (00-XX) 3 Functional analysis (46-XX) 3 Quantum theory (81-XX) 2 History and biography (01-XX) 2 General algebraic systems (08-XX) 2 Category theory; homological algebra (18-XX) 2 Topological groups, Lie groups (22-XX) 2 Functions of a complex variable (30-XX) 2 Approximations and expansions (41-XX) 2 Mechanics of deformable solids (74-XX) 1 Commutative algebra (13-XX) 1 Real functions (26-XX) 1 Measure and integration (28-XX) 1 Sequences, series, summability (40-XX) 1 Differential geometry (53-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Mechanics of particles and systems (70-XX) 1 Fluid mechanics (76-XX) 1 Classical thermodynamics, heat transfer (80-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.