# zbMATH — the first resource for mathematics

## Galil, Zvi

Compute Distance To:
 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: 155 Publications since 1974, including 4 Books
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 7 Ben-Amram, Amir M. 7 Margalit, Oded 7 Yung, Moti 5 Seiferas, Joel I. 4 Crochemore, Maxime 4 Megiddo, Nimrod 4 Spencer, Thomas H. 3 Alon, Noga M. 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 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, Michael 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 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 2 The Annals of Statistics 2 Journal of Algorithms 2 Lecture Notes in Computer Science 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

 132 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) 8 Information and communication theory, circuits (94-XX) 4 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)

#### Citations contained in zbMATH Open

133 Publications have been cited 1,537 times in 1,194 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.
1986
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
1981
NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037
Leven, Daniel; Galil, Zvi
1983
D-optimum weighing designs. Zbl 0466.62066
Galil, Z.; Kiefer, J.
1980
Time-space-optimal string matching. Zbl 0509.68101
Galil, Zvi; Seiferas, Joel
1983
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1997
Construction methods for D-optimum weighing designs when n=3(mod 4). Zbl 0489.62068
Galil, Z.; Kiefer, J.
1982
On the exponent of all pairs shortest path problem. Zbl 0877.68090
Alon, Noga; Galil, Zvi; Margalit, Oded
1997
An improved algorithm for approximate string matching. Zbl 0711.68048
Galil, Zvi; Park, Kunsoo
1990
Data structures and algorithms for approximate string matching. Zbl 0646.68078
Galil, Z.; Giancarlo, R.
1988
Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064
Galil, Zvi
1986
On the complexity of regular resolution and the Davis-Putnam procedure. Zbl 0385.68048
Galil, Zvi
1977
An almost linear-time algorithm for computing a dependency basis in a relational database. Zbl 0485.68090
Galil, Zvi
1982
Comparison of simplex designs for quadratic mixture models. Zbl 0372.62058
Galil, Z.; Kiefer, J.
1977
Comparison of rotatable designs for regression on balls. I. (quadratic). Zbl 0394.62058
Galil, Z.; Kiefer, J.
1977
Optimal parallel algorithms for string matching. Zbl 0588.68022
Galil, Zvi
1985
Better expanders and superconcentrators. Zbl 0641.68102
Alon, N.; Galil, Z.; Milman, V. D.
1987
A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032
Galil, Zvi; Park, Kunsoo
1990
On O(EV log V) algorithm for finding a maximal weighted matching in general graphs. Zbl 0589.68050
Galil, Zvi; Micali, Silvio; Gabow, Harold
1986
Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090
Galil, Zvi; Giancarlo, Raffaele
1989
Finding the vertex connectivity of graphs. Zbl 0446.68053
Galil, Zvi
1980
Parallel detection of all palindromes in a string. Zbl 0873.68039
Apostolico, Alberto; Breslauer, Dany; Galil, Zvi
1995
Hierarchies of complete problems. Zbl 0304.68044
Galil, Zvi
1976
Monotone switching circuits and Boolean matrix product. Zbl 0323.94019
Mehlhorn, K.; Galil, Z.
1976
On improving the worst case running time of the Boyer-Moore string matching algorithm. Zbl 0413.68041
Galil, Zvi
1979
Dynamic dictionary matching. Zbl 0942.68783
Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo
1994
Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707
Galil, Zvi; Park, Kunsoo
1992
Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053
Breslauer, D.; Galil, Z.
1995
All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081
Galil, Zvi; Margalit, Oded
1997
An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057
Breslauer, Dany; Galil, Zvi
1990
Comparison of design for quadratic regression of cubes. Zbl 0381.62062
Galil, Z.; Kiefer, J.
1977
Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1992
Sparsification – a technique for speeding up dynamic graph algorithms. (Extended abstract). Zbl 0977.68560
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1992
Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562
Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni
1992
Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658
Galil, Zvi; Mayer, Alain; Yung, Moti
1995
Pattern matching algorithms. Zbl 0874.68006
Apostolico, Alberto (ed.); Galil, Zvi (ed.)
1997
A linear-time on-line recognition algorithm for ”palstar”. Zbl 0365.68058
Galil, Zvi; Seiferas, Joel
1978
Cyclic ordering is NP-complete. Zbl 0383.68045
Galil, Zvi; Megiddo, Nimrod
1978
On finding most uniform spanning trees. Zbl 0645.05035
Galil, Zvi; Schieber, Baruch
1988
Time- and space-saving computer methods, related to Mitchell’s DETMAX, for finding D-optimum designs. Zbl 0459.62060
Galil, Z.; Kiefer, J.
1980
A lower bound for parallel string matching. Zbl 0756.68048
Breslauer, Dany; Galil, Zvi
1992
A fast selection algorithm and the problem of optimum distribution of effort. Zbl 0404.90062
Galil, Zvi; Megiddo, Nimrod
1979
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. Zbl 1133.68469
Franklin, Matthew; Galil, Zvi; Yung, Moti
2000
Alphabet-independent two-dimensional witness computation. Zbl 0861.68032
Galil, Zvi; Park, Kunsoo
1996
An $$O(EV\log^2V)$$ algorithm for the maximal flow problem. Zbl 0449.90094
1980
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
1982
Extrapolation designs and Phi//p-optimum designs for cubic regression on the q-ball. Zbl 0412.62055
Galil, Z.; Kiefer, J.
1979
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
1982
Improved processor bounds for combinatorial problems in RNC. Zbl 0685.68048
Galil, Z.; Pan, V.
1988
String matching in real time. Zbl 0454.68009
Galil, Zvi
1981
Optimum weighing designs. Zbl 0462.62059
Kiefer, J.; Galil, Z.
1980
Lower bounds on communication complexity. Zbl 0635.68034
Duris, Pavol; Galil, Zvi; Schnitger, Georg
1987
Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1996
Some open problems in the theory of computation as questions about two- way deterministic pushdown automaton languages. Zbl 0356.68064
Galil, Zvi
1977
Real-time streaming string-matching. Zbl 1339.68324
Breslauer, Dany; Galil, Zvi
2011
A time-space tradeoff for language recognition. Zbl 0533.68047
Dúriś, Pavol; Galil, Zvi
1984
Saving space in fast string-matching. Zbl 0446.68041
Galil, Zvi; Seiferas, Joel
1980
Open problems in stringology. Zbl 0607.68054
Galil, Zvi
1985
Faster tree pattern matching. Zbl 0806.68055
Dubiner, Moshe; Galil, Zvi; Magen, Edith
1994
Sparse dynamic programming. II: Convex and concave cost functions. Zbl 0816.90130
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1992
Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088
Galil, Zvi; Park, Kunsoo
1992
On the exact complexity of string matching: Upper bounds. Zbl 0761.68046
Galil, Zvi; Giancarlo, Raffaele
1992
Real-time algorithms for string-matching and palindrome recognition. Zbl 0365.68032
Galil, Zvi
1976
On pointers versus addresses. Zbl 0799.68114
Ben-Amram, Amir M.; Galil, Zvi
1992
An O(n $$2(m+n\,\log \,n)\log \,n)$$ min-cost flow algorithm. Zbl 0652.90039
Galil, Zvi; Tardos, Éva
1988
Separator based sparsification for dynamic planar graph algorithms. Zbl 1310.05197
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1993
All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089
Galil, Zvi; Margalit, Oded
1997
Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Zbl 0328.68047
Galil, Zvi
1976
Palindrome recognition in real time by a multitape Turing machine. Zbl 0386.03020
Galil, Zvi
1978
Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040
Galil, Zvi; Pan, Victor
1989
Fully dynamic planarity testing with applications. Zbl 1064.05502
Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil
1999
An $$O(V^{5/3}E^{2/3})$$ algorithm for the maximal flow problem. Zbl 0456.68044
Galil, Zvi
1980
Efficient parallel algorithms for linear recurrence computation. Zbl 0487.68028
Greenberg, Albert C.; Ladner, Richard E.; Paterson, Michael S.; Galil, Zvi
1982
Parallel string matching with k mismatches. Zbl 0636.68084
Galil, Zvi; Giancarlo, Raffaele
1987
Sparse dynamic programming. Zbl 0785.90094
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1990
On the exact complexity of string matching: Lower bounds. Zbl 0738.68042
Galil, Zvi; Giancarlo, Raffaele
1991
Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1998
Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053
Galil, Zvi; Margalit, Olded
1993
An efficient general-purpose parallel computer. Zbl 0515.68022
Galil, Zvi; Paul, Wolfgang J.
1983
Comparison of designs equivalent under one or two criteria. Zbl 0533.62063
Galil, Z.; Kiefer, J.
1983
Two tapes are better than one for nondeterministic machines. Zbl 0558.68045
Dúriś, Pavol; Galil, Zvi
1984
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
1989
Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030
Chaimovich, Mark; Freiman, Gregory; Galil, Zvi
1989
Fully dynamic algorithms for 2-edge connectivity. Zbl 0760.68022
Galil, Zvi; Italiano, Giuseppe F.
1992
Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557
Galil, Zvi; Yu, Xiangdong
1995
Real-time recognition of substring repetition and reversal. Zbl 0349.68035
Seiferas, Joel; Galil, Zvi
1977
On resolution with clauses of bounded size. Zbl 0368.68085
Galil, Zvi
1977
Comparison of Box-Draper and d-optimum designs for experiments with mixtures. Zbl 0369.62087
Galil, Z.; Kiefer, J.
1977
Two nonlinear lower bounds for on-line computations. Zbl 0589.68039
Ďuriš, Pavol; Galil, Zvi; Paul, Wolfgang; Reischuk, Ruediger
1984
On the characterization of D-optimum weighing designs for n$$\equiv 3(mod\,4)$$. Zbl 0598.62087
Galil, Z.; Kiefer, J.
1982
Improved string matching with k mismatches. Zbl 0608.68058
Galil, Zvi; Giancarlo, Raffaele
1985
Parallel algorithms for dynamic programming recurrences with more than $$O(1)$$ dependency. Zbl 0820.90122
Galil, Zvi; Park, Kunsoo
1994
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
Apostolico, Alberto (ed.); Galil, Zvi (ed.)
1985
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
1988
Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007
Galil, Zvi; Haber, Stuart; Yung, Moti
1989
Linear-time string-matching using only a fixed number of local storage locations. Zbl 0454.68008
Galil, Zvi; Seiferas, Joel
1981
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
1986
An almost linear-time algorithm for the dense subset-sum problem. Zbl 0736.68041
Galil, Zvi; Margalit, Oded
1991
Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117
Galil, Zvi; Italiano, Giuseppe F.
1991
Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080
Galil, Zvi; Italiano, Giuseppe F.
1993
Real-time streaming string-matching. Zbl 1398.68701
Breslauer, Dany; Galil, Zvi
2014
Forty years of text indexing. Zbl 1381.68067
Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S.
2013
Real-time streaming string-matching. Zbl 1339.68324
Breslauer, Dany; Galil, Zvi
2011
Three-dimensional periodicity and its application to pattern matching. Zbl 1087.68080
Galil, Zvi; Park, Jong Geun; Park, Kunsoo
2004
Topological lower bounds on algebraic random access machines. Zbl 1017.68057
Ben-Amram, Amir M.; Galil, Zvi
2001
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. Zbl 1133.68469
Franklin, Matthew; Galil, Zvi; Yung, Moti
2000
Fully dynamic planarity testing with applications. Zbl 1064.05502
Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil
1999
Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1998
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1997
On the exponent of all pairs shortest path problem. Zbl 0877.68090
Alon, Noga; Galil, Zvi; Margalit, Oded
1997
All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081
Galil, Zvi; Margalit, Oded
1997
Pattern matching algorithms. Zbl 0874.68006
Apostolico, Alberto; Galil, Zvi
1997
All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089
Galil, Zvi; Margalit, Oded
1997
Constant-time randomized parallel string matching. Zbl 0885.68078
Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech
1997
Alphabet-independent two-dimensional witness computation. Zbl 0861.68032
Galil, Zvi; Park, Kunsoo
1996
Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1996
Parallel detection of all palindromes in a string. Zbl 0873.68039
Apostolico, Alberto; Breslauer, Dany; Galil, Zvi
1995
Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053
Breslauer, D.; Galil, Z.
1995
Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658
Galil, Zvi; Mayer, Alain; Yung, Moti
1995
Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557
Galil, Zvi; Yu, Xiangdong
1995
On the power of the shift instruction. Zbl 0828.68074
Ben-Amram, Amir M.; Galil, Zvi
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
1995
A constant-time optimal parallel string-matching algorithm. Zbl 0885.68082
Galil, Zvi
1995
Dynamic dictionary matching. Zbl 0942.68783
Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo
1994
Faster tree pattern matching. Zbl 0806.68055
Dubiner, Moshe; Galil, Zvi; Magen, Edith
1994
Parallel algorithms for dynamic programming recurrences with more than $$O(1)$$ dependency. Zbl 0820.90122
Galil, Zvi; Park, Kunsoo
1994
Parallel detection of all palindromes in a string. Zbl 0941.68825
Apostolico, Alberto; Breslauer, Dany; Galil, Zvi
1994
Separator based sparsification for dynamic planar graph algorithms. Zbl 1310.05197
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.
1993
Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053
Galil, Zvi; Margalit, Olded
1993
Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080
Galil, Zvi; Italiano, Giuseppe F.
1993
Efficient comparison based string matching. Zbl 0783.68052
Breslauer, Dany; Galil, Zvi
1993
On the power of multiple reads in a chip. Zbl 0783.68061
Ďuriš, Pavol; Galil, Zvi
1993
Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707
Galil, Zvi; Park, Kunsoo
1992
Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1992
Sparsification – a technique for speeding up dynamic graph algorithms. (Extended abstract). Zbl 0977.68560
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
1992
Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562
Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni
1992
A lower bound for parallel string matching. Zbl 0756.68048
Breslauer, Dany; Galil, Zvi
1992
Sparse dynamic programming. II: Convex and concave cost functions. Zbl 0816.90130
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1992
Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088
Galil, Zvi; Park, Kunsoo
1992
On the exact complexity of string matching: Upper bounds. Zbl 0761.68046
Galil, Zvi; Giancarlo, Raffaele
1992
On pointers versus addresses. Zbl 0799.68114
Ben-Amram, Amir M.; Galil, Zvi
1992
Fully dynamic algorithms for 2-edge connectivity. Zbl 0760.68022
Galil, Zvi; Italiano, Giuseppe F.
1992
On the space complexity of some algorithms for sequence comparison. Zbl 0745.68060
Rabani, Yuval; Galil, Zvi
1992
On the exact complexity of string matching: Lower bounds. Zbl 0738.68042
Galil, Zvi; Giancarlo, Raffaele
1991
An almost linear-time algorithm for the dense subset-sum problem. Zbl 0736.68041
Galil, Zvi; Margalit, Oded
1991
Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117
Galil, Zvi; Italiano, Giuseppe F.
1991
A note on set union with arbitrary deunions. Zbl 0714.68039
Galil, Zvi; Italiano, Giuseppe F.
1991
Two lower bounds in asynchronous distributed computation. Zbl 0731.68043
Duris, Pavol; Galil, Zvi
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
1991
An almost linear-time algorithm for the dense subset-sum problem. Zbl 0769.68043
Galil, Zvi; Margalit, Oded
1991
An improved algorithm for approximate string matching. Zbl 0711.68048
Galil, Zvi; Park, Kunsoo
1990
A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032
Galil, Zvi; Park, Kunsoo
1990
An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057
Breslauer, Dany; Galil, Zvi
1990
Sparse dynamic programming. Zbl 0785.90094
Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.
1990
Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090
Galil, Zvi; Giancarlo, Raffaele
1989
Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040
Galil, Zvi; Pan, Victor
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
1989
Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030
Chaimovich, Mark; Freiman, Gregory; Galil, Zvi
1989
Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007
Galil, Zvi; Haber, Stuart; Yung, Moti
1989
On 3-pushdown graphs with large separators. Zbl 0726.05042
Galil, Z.; Kannan, R.; Szemerédi, E.
1989
An improved algorithm for approximate string matching. Zbl 0683.68034
Galil, Zvi; Park, Kunsoo
1989
Parallel algorithmic techniques for combinatorial computation. Zbl 0691.68037
Eppstein, David; Galil, Zvi
1989
Data structures and algorithms for approximate string matching. Zbl 0646.68078
Galil, Z.; Giancarlo, R.
1988
On finding most uniform spanning trees. Zbl 0645.05035
Galil, Zvi; Schieber, Baruch
1988
Improved processor bounds for combinatorial problems in RNC. Zbl 0685.68048
Galil, Z.; Pan, V.
1988
An O(n $$2(m+n\,\log \,n)\log \,n)$$ min-cost flow algorithm. Zbl 0652.90039
Galil, Zvi; Tardos, Éva
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
1988
Better expanders and superconcentrators. Zbl 0641.68102
Alon, N.; Galil, Z.; Milman, V. D.
1987
Lower bounds on communication complexity. Zbl 0635.68034
Duris, Pavol; Galil, Zvi; Schnitger, Georg
1987
Parallel string matching with k mismatches. Zbl 0636.68084
Galil, Zvi; Giancarlo, Raffaele
1987
Distributed algorithms in synchronous broadcasting networks. Zbl 0612.68007
Galil, Zvi; Landau, Gad M.; Yung, Mordechai M.
1987
Partitioned encryption and achieving simultaneity by partitioning. Zbl 0637.94015
Galil, Zvi; Yung, Moti
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.
1986
Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064
Galil, Zvi
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
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
1986
Optimal parallel algorithms for string matching. Zbl 0588.68022
Galil, Zvi
1985
Open problems in stringology. Zbl 0607.68054
Galil, Zvi
1985
Improved string matching with k mismatches. Zbl 0608.68058
Galil, Zvi; Giancarlo, Raffaele
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
Apostolico, Alberto; Galil, Zvi
1985
Computing $$D$$-optimum weighing designs: where statistics combinatorics, and computation meet. Zbl 1373.62397
Galil, Zvi
1985
A time-space tradeoff for language recognition. Zbl 0533.68047
Dúriś, Pavol; Galil, Zvi
1984
Two tapes are better than one for nondeterministic machines. Zbl 0558.68045
Dúriś, Pavol; Galil, Zvi
1984
Two nonlinear lower bounds for on-line computations. Zbl 0589.68039
Ďuriš, Pavol; Galil, Zvi; Paul, Wolfgang; Reischuk, Ruediger
1984
NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037
Leven, Daniel; Galil, Zvi
1983
Time-space-optimal string matching. Zbl 0509.68101
Galil, Zvi; Seiferas, Joel
1983
An efficient general-purpose parallel computer. Zbl 0515.68022
Galil, Zvi; Paul, Wolfgang J.
1983
Comparison of designs equivalent under one or two criteria. Zbl 0533.62063
Galil, Z.; Kiefer, J.
1983
Construction methods for D-optimum weighing designs when n=3(mod 4). Zbl 0489.62068
Galil, Z.; Kiefer, J.
1982
An almost linear-time algorithm for computing a dependency basis in a relational database. Zbl 0485.68090
Galil, Zvi
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
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
1982
Efficient parallel algorithms for linear recurrence computation. Zbl 0487.68028
Greenberg, Albert C.; Ladner, Richard E.; Paterson, Michael S.; Galil, Zvi
1982
On the characterization of D-optimum weighing designs for n$$\equiv 3(mod\,4)$$. Zbl 0598.62087
Galil, Z.; Kiefer, J.
1982
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
1981
String matching in real time. Zbl 0454.68009
Galil, Zvi
1981
Linear-time string-matching using only a fixed number of local storage locations. Zbl 0454.68008
Galil, Zvi; Seiferas, Joel
1981
On the theoretical efficiency of various network flow algorithms. Zbl 0464.68044
Galil, Zvi
1981
D-optimum weighing designs. Zbl 0466.62066
Galil, Z.; Kiefer, J.
1980
Finding the vertex connectivity of graphs. Zbl 0446.68053
Galil, Zvi
1980
...and 33 more Documents
all top 5

#### Cited by 1,730 Authors

 28 Galil, Zvi 20 Rytter, Wojciech 19 Crochemore, Maxime 15 Amir, Amihood 15 Park, Kunsoo 13 Apostolico, Alberto 13 Breslauer, Dany 13 Lingas, Andrzej 13 Link, Sebastian 11 Iliopoulos, Costas S. 10 Inenaga, Shunsuke 10 Kowalski, Dariusz R. 10 Punnen, Abraham P. 10 Rauch Henzinger, Monika 10 Schwarzmann, Alexander A. 9 Alon, Noga M. 9 Gąsieniec, Leszek Antoni 9 Grossi, Roberto 9 Landau, Gad M. 9 Mandal, Nripes Kumar 9 Pan, Victor Yakovlevich 9 Paulusma, Daniël 9 Radoszewski, Jakub 9 Tarjan, Robert Endre 8 de Figueiredo, Celina M. Herrera 8 Kolpakov, Roman M. 8 Kounias, Stratis 7 Hromkovič, Juraj 7 Mignosi, Filippo 7 Pal, Manisha 7 Porat, Ely 7 Takaoka, Tadao 7 Takeda, Masayuki 7 Wigderson, Avi 7 Wong, Chi Song 6 Bannai, Hideo 6 Charalampopoulos, Panagiotis 6 Chlebus, Bogdan Stanislaw 6 Eppstein, David Arthur 6 Golovach, Petr A. 6 Heiligers, Berthold 6 Italiano, Giuseppe Francesco 6 Kiefer, Jack Carl 6 Kociumaka, Tomasz 6 Kucherov, Gregory 6 Lecroq, Thierry 6 Pissis, Solon P. 6 Pukelsheim, Friedrich 6 Ukkonen, Esko 6 Vishkin, Uzi 5 Afraimovich, L. G. 5 Baeza-Yates, Ricardo A. 5 Baswana, Surender 5 Chudnovsky, Maria 5 Dehghan, Ali A. 5 Draper, Norman R. 5 Drezner, Zvi 5 Ďuriš, Pavol 5 Gawrychowski, Paweł 5 Georgiou, Chryssis 5 Giancarlo, Raffaele 5 Goldreich, Oded 5 Hartmann, Sven 5 Luccio, Fabrizio 5 Masaro, Joseph C. 5 Navarro, Gonzalo 5 Neubauer, Michael G. 5 Schaudt, Oliver 5 Seiferas, Joel I. 5 Shinohara, Ayumi 5 Waleń, Tomasz 5 Zhong, Mingxian 4 Bille, Philip 4 Blanchet-Sadri, Francine 4 Brimberg, Jack 4 Brimkov, Valentin E. 4 Chadjiconstantinidis, Stathis 4 Chao, Kunmao 4 Chrobak, Marek 4 Fernández-Baca, David 4 Fomin, Fedor V. 4 Ibarra, Oscar H. 4 Kratsch, Dieter 4 Levy, Avivit 4 Machado, Raphael Carlos Santos 4 Mehlhorn, Kurt 4 Mladenović, Nenad 4 Mukerjee, Rahul 4 Myers, Eugene W. 4 Paschos, Vangelis Th. 4 Persson, Mia 4 Pettie, Seth 4 Reif, John H. 4 Salhi, Said 4 Shur, Arseny M. 4 Tamir, Arie 4 Urquhart, Alasdair 4 van Iersel, Leo 4 Wegener, Ingo 4 Yang, Boting ...and 1,630 more Authors
all top 5

#### Cited in 188 Serials

 194 Theoretical Computer Science 90 Information Processing Letters 78 Algorithmica 57 Discrete Applied Mathematics 52 Journal of Computer and System Sciences 40 Journal of Statistical Planning and Inference 35 Information and Computation 24 Journal of Discrete Algorithms 19 European Journal of Operational Research 17 Communications in Statistics. Theory and Methods 16 Discrete Mathematics 14 Statistics & Probability Letters 14 International Journal of Foundations of Computer Science 13 Combinatorica 13 International Journal of Computer Mathematics 13 Linear Algebra and its Applications 12 SIAM Journal on Computing 12 Computational Complexity 12 Theory of Computing Systems 11 Operations Research Letters 11 Distributed Computing 10 Acta Informatica 10 Journal of Combinatorial Optimization 8 Mathematical Systems Theory 8 Journal of Complexity 7 Artificial Intelligence 7 Information Sciences 7 Journal of Combinatorial Theory. Series B 7 European Journal of Combinatorics 7 Mathematical Programming. Series A. Series B 7 Annals of Mathematics and Artificial Intelligence 6 Computers & Mathematics with Applications 6 Networks 6 SIAM Journal on Algebraic and Discrete Methods 6 Annals of Operations Research 6 Parallel Algorithms and Applications 5 Computing 5 Computers & Operations Research 5 Automation and Remote Control 5 Computational Statistics and Data Analysis 4 Metrika 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 Algorithms 3 The Canadian Journal of Statistics 3 Linear and Multilinear Algebra 3 The Annals of Statistics 3 BIT 3 International Journal of Game Theory 3 Transactions of the American Mathematical Society 3 Annals of Pure and Applied Logic 3 Discrete & Computational Geometry 3 Journal of Automated Reasoning 3 Journal of Mathematical Sciences (New York) 3 Journal of Applied Mathematics and Computing 3 Mathematics in Computer Science 3 Computer Science Review 2 Journal of Mathematical Analysis and Applications 2 Applied Mathematics and Computation 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 Journal of Cryptology 2 International Journal of Computational Geometry & Applications 2 Communications in Statistics. Simulation and Computation 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 The Electronic Journal of Combinatorics 2 Journal of Heuristics 2 Mathematical Methods of Operations Research 2 Journal of Discrete Mathematical Sciences & Cryptography 2 RAIRO. Theoretical Informatics and Applications 2 Discrete Optimization 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 1 Moscow University Mathematics Bulletin 1 Bulletin of Mathematical Biology 1 Advances in Mathematics 1 Algebra and Logic 1 Algebra Universalis 1 Annales de l’Institut Fourier 1 Annals of the Institute of Statistical Mathematics 1 Automatica 1 Fuzzy Sets and Systems ...and 88 more Serials
all top 5

#### Cited in 40 Fields

 842 Computer science (68-XX) 311 Combinatorics (05-XX) 181 Operations research, mathematical programming (90-XX) 126 Statistics (62-XX) 56 Mathematical logic and foundations (03-XX) 51 Information and communication theory, circuits (94-XX) 41 Numerical analysis (65-XX) 32 Biology and other natural sciences (92-XX) 30 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 23 Linear and multilinear algebra; matrix theory (15-XX) 12 Number theory (11-XX) 10 Probability theory and stochastic processes (60-XX) 8 Field theory and polynomials (12-XX) 8 Convex and discrete geometry (52-XX) 7 Group theory and generalizations (20-XX) 7 Systems theory; control (93-XX) 6 Order, lattices, ordered algebraic structures (06-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 4 Geometry (51-XX) 3 Functional analysis (46-XX) 2 General and overarching topics; collections (00-XX) 2 General algebraic systems (08-XX) 2 Category theory; homological algebra (18-XX) 2 Functions of a complex variable (30-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Approximations and expansions (41-XX) 2 Manifolds and cell complexes (57-XX) 2 Mechanics of deformable solids (74-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 History and biography (01-XX) 1 Topological groups, Lie groups (22-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 Fluid mechanics (76-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Quantum theory (81-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.