Zvi Galil - Author Profile

Edit Profile

Galil, Zvi

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,397 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

142 Publications have been cited 2,085 times in 1,623 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.	106	1986
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045 Gabber, Ofer; Galil, Zvi	102	1981
NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037 Leven, Daniel; Galil, Zvi	97	1983
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon	71	1997
D-optimum weighing designs. Zbl 0466.62066 Galil, Z.; Kiefer, J.	55	1980
Time-space-optimal string matching. Zbl 0509.68101 Galil, Zvi; Seiferas, Joel	54	1983
On the exponent of all pairs shortest path problem. Zbl 0877.68090 Alon, Noga; Galil, Zvi; Margalit, Oded	44	1997
Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064 Galil, Zvi	42	1986
Pattern matching algorithms. Zbl 0874.68006	37	1997
An improved algorithm for approximate string matching. Zbl 0711.68048 Galil, Zvi; Park, Kunsoo	35	1990
Improved string matching with k mismatches. Zbl 0608.68058 Galil, Zvi; Giancarlo, Raffaele	33	1985
Data structures and algorithms for approximate string matching. Zbl 0646.68078 Galil, Z.; Giancarlo, R.	33	1988
Construction methods for D-optimum weighing designs when n=3(mod 4). Zbl 0489.62068 Galil, Z.; Kiefer, J.	33	1982
On the complexity of regular resolution and the Davis-Putnam procedure. Zbl 0385.68048 Galil, Zvi	32	1977
Sparsification – a technique for speeding up dynamic graph algorithms. (Extended abstract). Zbl 0977.68560 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon	29	1992
Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658 Galil, Zvi; Mayer, Alain; Yung, Moti	29	1995
Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562 Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni	27	1992
Better expanders and superconcentrators. Zbl 0641.68102 Alon, N.; Galil, Z.; Milman, V. D.	26	1987
Parallel detection of all palindromes in a string. Zbl 0873.68039 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi	26	1995
Optimal parallel algorithms for string matching. Zbl 0588.68022 Galil, Zvi	26	1985
Comparison of rotatable designs for regression on balls. I. (quadratic). Zbl 0394.62058 Galil, Z.; Kiefer, J.	26	1977
Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.	25	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	25	1986
An almost linear-time algorithm for computing a dependency basis in a relational database. Zbl 0485.68090 Galil, Zvi	25	1982
Comparison of simplex designs for quadratic mixture models. Zbl 0372.62058 Galil, Z.; Kiefer, J.	25	1977
Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707 Galil, Zvi; Park, Kunsoo	24	1992
Monotone switching circuits and Boolean matrix product. Zbl 0323.94019 Mehlhorn, K.; Galil, Z.	21	1976
A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032 Galil, Zvi; Park, Kunsoo	21	1990
Dynamic dictionary matching. Zbl 0942.68783 Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo	21	1994
Cyclic ordering is NP-complete. Zbl 0383.68045 Galil, Zvi; Megiddo, Nimrod	21	1978
Lower bounds on communication complexity. Zbl 0635.68034 Duris, Pavol; Galil, Zvi; Schnitger, Georg	20	1987
All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081 Galil, Zvi; Margalit, Oded	20	1997
Finding the vertex connectivity of graphs. Zbl 0446.68053 Galil, Zvi	20	1980
Hierarchies of complete problems. Zbl 0304.68044 Galil, Zvi	19	1976
Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090 Galil, Zvi; Giancarlo, Raffaele	19	1989
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. Zbl 1133.68469 Franklin, Matthew; Galil, Zvi; Yung, Moti	19	2000
Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053 Breslauer, D.; Galil, Z.	19	1995
On improving the worst case running time of the Boyer-Moore string matching algorithm. Zbl 0413.68041 Galil, Zvi	19	1979
Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.	18	1996
Comparison of design for quadratic regression of cubes. Zbl 0381.62062 Galil, Z.; Kiefer, J.	18	1977
Separator based sparsification for dynamic planar graph algorithms. Zbl 1310.05197 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.	18	1993
An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057 Breslauer, Dany; Galil, Zvi	17	1990
On finding most uniform spanning trees. Zbl 0645.05035 Galil, Zvi; Schieber, Baruch	17	1988
An \(O(EV\log^2V)\) algorithm for the maximal flow problem. Zbl 0449.90094 Galil, Zvi; Naamad, Amnon	17	1980
A linear-time on-line recognition algorithm for ”palstar”. Zbl 0365.68058 Galil, Zvi; Seiferas, Joel	17	1978
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
A fast selection algorithm and the problem of optimum distribution of effort. Zbl 0404.90062 Galil, Zvi; Megiddo, Nimrod	16	1979
Real-time streaming string-matching. Zbl 1339.68324 Breslauer, Dany; Galil, Zvi	15	2011
All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089 Galil, Zvi; Margalit, Oded	15	1997
String matching in real time. Zbl 0454.68009 Galil, Zvi	15	1981
Time- and space-saving computer methods, related to Mitchell’s DETMAX, for finding D-optimum designs. Zbl 0459.62060 Galil, Z.; Kiefer, J.	15	1980
Improved processor bounds for combinatorial problems in RNC. Zbl 0685.68048 Galil, Z.; Pan, V.	14	1988
A lower bound for parallel string matching. Zbl 0756.68048 Breslauer, Dany; Galil, Zvi	13	1992
Open problems in stringology. Zbl 0607.68054 Galil, Zvi	13	1985
Alphabet-independent two-dimensional witness computation. Zbl 0861.68032 Galil, Zvi; Park, Kunsoo	13	1996
Some open problems in the theory of computation as questions about two- way deterministic pushdown automaton languages. Zbl 0356.68064 Galil, Zvi	13	1977
Extrapolation designs and \(\Phi_p\)-optimum designs for cubic regression on the \(q\)-ball. Zbl 0412.62055 Galil, Z.; Kiefer, J.	13	1979
An O(n \(2(m+n\,\log \,n)\log \,n)\) min-cost flow algorithm. Zbl 0652.90039 Galil, Zvi; Tardos, Éva	12	1988
Sparse dynamic programming. II: Convex and concave cost functions. Zbl 0816.90130 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.	12	1992
Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.	12	1998
On the exact complexity of string matching: Upper bounds. Zbl 0761.68046 Galil, Zvi; Giancarlo, Raffaele	11	1992
An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem. Zbl 0456.68044 Galil, Zvi	11	1980
Optimum weighing designs. Zbl 0462.62059 Kiefer, J.; Galil, Z.	11	1980
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
Fully dynamic planarity testing with applications. Zbl 1064.05502 Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil	11	1999
A time-space tradeoff for language recognition. Zbl 0533.68047 Dúriś, Pavol; Galil, Zvi	11	1984
Real-time streaming string-matching. Zbl 1398.68701 Breslauer, Dany; Galil, Zvi	10	2014
Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088 Galil, Zvi; Park, Kunsoo	10	1992
Optimal parallel algorithms for periods, palindromes and squares (extended abstract). Zbl 1425.68466 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi	10	1992
Faster tree pattern matching. Zbl 0806.68055 Dubiner, Moshe; Galil, Zvi; Magen, Edith	10	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	10	1985
Saving space in fast string-matching. Zbl 0446.68041 Galil, Zvi; Seiferas, Joel	10	1980
Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080 Galil, Zvi; Italiano, Giuseppe F.	9	1993
Parallel string matching with k mismatches. Zbl 0636.68084 Galil, Zvi; Giancarlo, Raffaele	9	1987
On pointers versus addresses. Zbl 0799.68114 Ben-Amram, Amir M.; Galil, Zvi	9	1992
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
Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117 Galil, Zvi; Italiano, Giuseppe F.	8	1991
Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Zbl 0328.68047 Galil, Zvi	8	1976
An almost linear-time algorithm for the dense subset-sum problem. Zbl 0736.68041 Galil, Zvi; Margalit, Oded	8	1991
An improved algorithm for approximate string matching. Zbl 0683.68034 Galil, Zvi; Park, Kunsoo	7	1989
Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007 Galil, Zvi; Haber, Stuart; Yung, Moti	7	1989
Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030 Chaimovich, Mark; Freiman, Gregory; Galil, Zvi	7	1989
Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency. Zbl 0820.90122 Galil, Zvi; Park, Kunsoo	7	1994
On the power of the shift instruction. Zbl 0828.68074 Ben-Amram, Amir M.; Galil, Zvi	7	1995
Sparse dynamic programming. Zbl 0785.90094 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.	7	1990
Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053 Galil, Zvi; Margalit, Olded	7	1993
On resolution with clauses of bounded size. Zbl 0368.68085 Galil, Zvi	7	1977
Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557 Galil, Zvi; Yu, Xiangdong	7	1995
Efficient parallel algorithms for linear recurrence computation. Zbl 0487.68028 Greenberg, Albert C.; Ladner, Richard E.; Paterson, Michael S.; Galil, Zvi	7	1982
Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040 Galil, Zvi; Pan, Victor	7	1989
On the exact complexity of string matching: Lower bounds. Zbl 0738.68042 Galil, Zvi; Giancarlo, Raffaele	7	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
An efficient general-purpose parallel computer. Zbl 0515.68022 Galil, Zvi; Paul, Wolfgang J.	6	1983
Fully dynamic algorithms for 2-edge connectivity. Zbl 0760.68022 Galil, Zvi; Italiano, Giuseppe F.	5	1992
On 3-pushdown graphs with large separators. Zbl 0726.05042 Galil, Z.; Kannan, R.; Szemerédi, E.	5	1989
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	5	1984
Comparison of Box-Draper and d-optimum designs for experiments with mixtures. Zbl 0369.62087 Galil, Z.; Kiefer, J.	5	1977
Comparison of designs equivalent under one or two criteria. Zbl 0533.62063 Galil, Z.; Kiefer, J.	5	1983
Real-time streaming string-matching. Zbl 1398.68701 Breslauer, Dany; Galil, Zvi	10	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	15	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.	2	2002
A generalization of a lower bound technique due to Fredman and Saks. Zbl 0992.68034 Ben-Amram, A. M.; Galil, Z.	4	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	19	2000
Fully dynamic planarity testing with applications. Zbl 1064.05502 Galil, Zvi; Italiano, Giuseppe F.; Sarnak, Neil	11	1999
Separator-based sparsification. II: Edge and vertex connectivity. Zbl 0914.68042 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.	12	1998
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon	71	1997
On the exponent of all pairs shortest path problem. Zbl 0877.68090 Alon, Noga; Galil, Zvi; Margalit, Oded	44	1997
Pattern matching algorithms. Zbl 0874.68006	37	1997
All pairs shortest distances for graphs with small integer length edges. Zbl 0879.68081 Galil, Zvi; Margalit, Oded	20	1997
All pairs shortest paths for graphs with small integer length edges. Zbl 0877.68089 Galil, Zvi; Margalit, Oded	15	1997
Constant-time randomized parallel string matching. Zbl 0885.68078 Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech	4	1997
Separator based sparsification. I: Planarity testing and minimum spanning trees. Zbl 0846.68079 Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.	18	1996
Alphabet-independent two-dimensional witness computation. Zbl 0861.68032 Galil, Zvi; Park, Kunsoo	13	1996
Resolving message complexity of Byzantine agreement and beyond. Zbl 0938.68658 Galil, Zvi; Mayer, Alain; Yung, Moti	29	1995
Parallel detection of all palindromes in a string. Zbl 0873.68039 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi	26	1995
Finding all periods and initial palindromes of a string in parallel. Zbl 0833.68053 Breslauer, D.; Galil, Z.	19	1995
On the power of the shift instruction. Zbl 0828.68074 Ben-Amram, Amir M.; Galil, Zvi	7	1995
Short length versions of Menger’s theorem. (Extended abstract). Zbl 0978.68557 Galil, Zvi; Yu, Xiangdong	7	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
Lower bounds on algebraic random access machines. Zbl 1412.68057 Ben-Amram, Amir M.; Galil, Zvi	1	1995
Dynamic dictionary matching. Zbl 0942.68783 Amir, Amihood; Farach, Martin; Galil, Zvi; Giancarlo, Raffaele; Park, Kunsoo	21	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	7	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.	18	1993
Maintaining the 3-edge-connected components of a graph on-line. Zbl 0767.68080 Galil, Zvi; Italiano, Giuseppe F.	9	1993
Witnesses for Boolean matrix multiplication and for transitive closure. Zbl 0785.65053 Galil, Zvi; Margalit, Olded	7	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	29	1992
Witnesses for Boolean matrix multiplication and for shortest paths. Zbl 0977.68562 Alon, Noga; Galil, Zvi; Margalit, Oded; Naor, Moni	27	1992
Sparse dynamic programming I: Linear cost functions. Zbl 0807.90120 Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F.	25	1992
Truly alphabet-independent two-dimensional pattern matching. Zbl 0942.68707 Galil, Zvi; Park, Kunsoo	24	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.	12	1992
On the exact complexity of string matching: Upper bounds. Zbl 0761.68046 Galil, Zvi; Giancarlo, Raffaele	11	1992
Dynamic programming with convexity, concavity and sparsity. Zbl 0763.90088 Galil, Zvi; Park, Kunsoo	10	1992
Optimal parallel algorithms for periods, palindromes and squares (extended abstract). Zbl 1425.68466 Apostolico, Alberto; Breslauer, Dany; Galil, Zvi	10	1992
On pointers versus addresses. Zbl 0799.68114 Ben-Amram, Amir M.; Galil, Zvi	9	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
Combinatorial pattern matching. 3rd annual symposium, Tucson, AZ, USA, April 29 – May 1, 1992. Proceedings. Zbl 0825.00058	1	1992
Maintaining biconnected components of dynamic planar graphs. Zbl 0764.68117 Galil, Zvi; Italiano, Giuseppe F.	8	1991
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	7	1991
Two lower bounds in asynchronous distributed computation. Zbl 0731.68043 Duris, Pavol; Galil, Zvi	4	1991
A note on set union with arbitrary deunions. Zbl 0714.68039 Galil, Zvi; Italiano, Giuseppe F.	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	35	1990
A linear-time algorithm for concave one-dimensional dynamic programming. Zbl 0694.68032 Galil, Zvi; Park, Kunsoo	21	1990
An optimal O(log log n) time parallel string matching algorithm. Zbl 0711.68057 Breslauer, Dany; Galil, Zvi	17	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	2	1990
Speeding up dynamic programming with applications to molecular biology. Zbl 0673.90090 Galil, Zvi; Giancarlo, Raffaele	19	1989
An improved algorithm for approximate string matching. Zbl 0683.68034 Galil, Zvi; Park, Kunsoo	7	1989
Minimum-knowledge interactive proofs for decision problems. Zbl 0678.94007 Galil, Zvi; Haber, Stuart; Yung, Moti	7	1989
Solving dense subset-sum problems by using analytical number theory. Zbl 0686.68030 Chaimovich, Mark; Freiman, Gregory; Galil, Zvi	7	1989
Parallel evaluation of the determinant and of the inverse of a matrix. Zbl 0664.68040 Galil, Zvi; Pan, Victor	7	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
On 3-pushdown graphs with large separators. Zbl 0726.05042 Galil, Z.; Kannan, R.; Szemerédi, E.	5	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.	33	1988
On finding most uniform spanning trees. Zbl 0645.05035 Galil, Zvi; Schieber, Baruch	17	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	12	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.	26	1987
Lower bounds on communication complexity. Zbl 0635.68034 Duris, Pavol; Galil, Zvi; Schnitger, Georg	20	1987
Parallel string matching with k mismatches. Zbl 0636.68084 Galil, Zvi; Giancarlo, Raffaele	9	1987
Partitioned encryption and achieving simultaneity by partitioning. Zbl 0637.94015 Galil, Zvi; Yung, Moti	4	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.	106	1986
Efficient algorithms for finding maximum matching in graphs. Zbl 0606.68064 Galil, Zvi	42	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	25	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
Improved string matching with k mismatches. Zbl 0608.68058 Galil, Zvi; Giancarlo, Raffaele	33	1985
Optimal parallel algorithms for string matching. Zbl 0588.68022 Galil, Zvi	26	1985
Open problems in stringology. Zbl 0607.68054 Galil, Zvi	13	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	10	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	5	1984
NP-completeness of finding the chromatic index of regular graphs. Zbl 0509.68037 Leven, Daniel; Galil, Zvi	97	1983
Time-space-optimal string matching. Zbl 0509.68101 Galil, Zvi; Seiferas, Joel	54	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
Efficient algorithms for finding maximal matching in graphs. Zbl 0527.68050 Galil, Zvi	3	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	25	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
...and 42 more Documents

all cited Publications top 5 cited Publications

all top 5

Cited by 2,272 Authors

31	Galil, Zvi
26	Rytter, Wojciech
25	Amir, Amihood
25	Crochemore, Maxime
20	Apostolico, Alberto
19	Lingas, Andrzej
18	Iliopoulos, Costas S.
16	Park, Kunsoo
16	Rauch Henzinger, Monika
15	Kowalski, Dariusz R.
15	Porat, Ely
15	Radoszewski, Jakub
14	Landau, Gad M.
14	Link, Sebastian
14	Paulusma, Daniël
13	Breslauer, Dany
13	Eppstein, David Arthur
13	Inenaga, Shunsuke
12	Gąsieniec, Leszek Antoni
12	Grossi, Roberto
12	Kociumaka, Tomasz
12	Pissis, Solon P.
11	Charalampopoulos, Panagiotis
11	Chlebus, Bogdan Stanislaw
11	Mandal, Nripes Kumar
11	Schwarzmann, Alexander A.
11	Tarjan, Robert Endre
11	Wigderson, Avi
10	Alon, Noga
10	Gawrychowski, Paweł
10	Punnen, Abraham P.
10	Takeda, Masayuki
9	Chan, Timothy Moon-Yew
9	de Figueiredo, Celina M. Herrera
9	Italiano, Giuseppe Francesco
9	Kolpakov, Roman M.
9	Pal, Manisha
9	Pan, Victor Yakovlevich
8	Bannai, Hideo
8	Bille, Philip
8	Hromkovič, Juraj
8	Kounias, Stratis
8	Levy, Avivit
8	Mignosi, Filippo
8	Sankowski, Piotr
8	Shur, Arseny M.
8	Starikovskaya, Tatiana A.
8	Takaoka, Tadao
8	Vishkin, Uzi
7	Baeza-Yates, Ricardo A.
7	Baswana, Surender
7	Duan, Ran
7	Fernández-Baca, David
7	Kucherov, Gregory
7	Lecroq, Thierry
7	Navarro, Gonzalo
7	Shinohara, Ayumi
7	Sokol, Dina
7	Ukkonen, Esko
7	Vassilevska Williams, Virginia
7	Waleń, Tomasz
7	Wong, Chi Song
7	Zuckerman, David
6	Georgiou, Chryssis
6	Giancarlo, Raffaele
6	Goldreich, Oded
6	Golovach, Petr A.
6	Gørtz, Inge Li
6	Heiligers, Berthold
6	Huda, Shahariar
6	Kiefer, Jack Carl
6	Kopelowitz, Tsvi
6	Pukelsheim, Friedrich
6	Seiferas, Joel I.
6	Vildhøj, Hjalte Wedel
6	Wegener, Ingo
5	Afraimovich, L. G.
5	Alzamel, Mai
5	Brimkov, Valentin E.
5	Bringmann, Karl
5	Butman, Ayelet
5	Chudnovsky, Maria
5	Czumaj, Artur
5	Dehghan, Ali A.
5	Draper, Norman R.
5	Drezner, Zvi
5	Ďuriš, Pavol
5	Funakoshi, Mitsuru
5	Golan, Shay
5	Grigorescu, Elena
5	Hartmann, Sven
5	Holm, Jacob
5	Karczmarz, Adam
5	Lewenstein, Moshe
5	Li, Ming
5	Luccio, Fabrizio
5	Machado, Raphael Carlos Santos
5	Masaro, Joseph C.
5	Muthukrishnan, S. Muthu
5	Neubauer, Michael G.
...and 2,172 more Authors

all top 5

Cited in 216 Serials

215	Theoretical Computer Science
104	Information Processing Letters
93	Algorithmica
67	Discrete Applied Mathematics
59	Journal of Computer and System Sciences
41	Journal of Statistical Planning and Inference
39	Information and Computation
27	Journal of Discrete Algorithms
21	European Journal of Operational Research
19	Discrete Mathematics
19	Communications in Statistics. Theory and Methods
16	SIAM Journal on Computing
15	International Journal of Foundations of Computer Science
14	Statistics & Probability Letters
14	Combinatorica
14	Theory of Computing Systems
13	International Journal of Computer Mathematics
13	Linear Algebra and its Applications
13	Computational Complexity
12	Operations Research Letters
12	Distributed Computing
12	Journal of Combinatorial Optimization
10	Acta Informatica
9	Artificial Intelligence
9	Information Sciences
8	Mathematical Systems Theory
8	Journal of Complexity
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
6	ACM Transactions on Algorithms
5	Computing
5	Random Structures & Algorithms
5	Automation and Remote Control
5	Journal of the ACM
5	ACM Journal of Experimental Algorithmics
4	Metrika
4	International Journal of Game Theory
4	Journal of Combinatorial Theory. Series A
4	Kybernetika
4	Discrete & Computational Geometry
4	Journal of Parallel and Distributed Computing
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	Journal of Graph Theory
3	Transactions of the American Mathematical Society
3	Annals of Pure and Applied Logic
3	Journal of Automated Reasoning
3	SIAM Journal on Discrete Mathematics
3	International Journal of Computational Geometry & Applications
3	Communications in Statistics. Simulation and Computation
3	SIAM Journal on Scientific Computing
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	Computer Science Review
2	Journal of Mathematical Analysis and Applications
2	Physica A
2	Journal of Soviet Mathematics
2	Naval Research Logistics
2	Statistics
2	Graphs and Combinatorics
2	Journal of Symbolic Computation
2	Applied Mathematics Letters
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	Statistical Papers
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	RAIRO. Operations Research
2	Discrete Optimization
2	Logical Methods in Computer Science
2	Nonlinear Analysis. Hybrid Systems
...and 116 more Serials

all top 5

Cited in 42 Fields

1,201	Computer science (68-XX)
454	Combinatorics (05-XX)
220	Operations research, mathematical programming (90-XX)
137	Statistics (62-XX)
69	Information and communication theory, circuits (94-XX)
66	Mathematical logic and foundations (03-XX)
44	Numerical analysis (65-XX)
42	Biology and other natural sciences (92-XX)
41	Game theory, economics, finance, and other social and behavioral sciences (91-XX)
27	Linear and multilinear algebra; matrix theory (15-XX)
13	Probability theory and stochastic processes (60-XX)
12	Number theory (11-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)
8	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	Approximations and expansions (41-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	Mechanics of deformable solids (74-XX)
1	Commutative algebra (13-XX)
1	Real functions (26-XX)
1	Measure and integration (28-XX)
1	Ordinary differential equations (34-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)

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.