| 2004 |
|---|
| 174 | EE | Richard Cole,
Zvi Galil,
Ramesh Hariharan,
S. Muthukrishnan,
Kunsoo Park:
Parallel two dimensional witness computation.
Inf. Comput. 188(1): 20-67 (2004) |
| 173 | EE | Zvi Galil,
Jong Geun Park,
Kunsoo Park:
Three-Dimensional Periodicity and Its Application to Pattern Matching.
SIAM J. Discrete Math. 18(2): 362-381 (2004) |
| 2002 |
|---|
| 172 | EE | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds for Dynamic Data Structures on Algebraic RAMs.
Algorithmica 32(3): 364-395 (2002) |
| 2001 |
|---|
| 171 | EE | Amir M. Ben-Amram,
Zvi Galil:
A Generalization of a Lower Bound Technique due to Fredman and Saks.
Algorithmica 30(1): 34-66 (2001) |
| 170 | EE | Amir M. Ben-Amram,
Zvi Galil:
Topological Lower Bounds on Algebraic Random Access Machines.
SIAM J. Comput. 31(3): 722-761 (2001) |
| 2000 |
|---|
| 169 | EE | Matthew K. Franklin,
Zvi Galil,
Moti Yung:
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems.
J. ACM 47(2): 225-243 (2000) |
| 1999 |
|---|
| 168 | EE | Zvi Galil,
Giuseppe F. Italiano,
Neil Sarnak:
Fully Dynamic Planarity Testing with Applications.
J. ACM 46(1): 28-91 (1999) |
| 1998 |
|---|
| 167 | | David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
Thomas H. Spencer:
Separator-Based Sparsification II: Edge and Vertex Connectivity.
SIAM J. Comput. 28(1): 341-381 (1998) |
| 1997 |
|---|
| 166 | EE | Zvi Galil,
Jong Geun Park,
Kunsoo Park:
Three-Dimensional Pattern Matching.
SPAA 1997: 53-62 |
| 165 | | Zvi Galil,
Oded Margalit:
All Pairs Shortest Distances for Graphs with Small Integer Length Edges.
Inf. Comput. 134(2): 103-139 (1997) |
| 164 | EE | David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
Amnon Nissenzweig:
Sparsification - a technique for speeding up dynamic graph algorithms.
J. ACM 44(5): 669-696 (1997) |
| 163 | | Zvi Galil,
Oded Margalit:
All Pairs Shortest Paths for Graphs with Small Integer Length Edges.
J. Comput. Syst. Sci. 54(2): 243-254 (1997) |
| 162 | | Noga Alon,
Zvi Galil,
Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem.
J. Comput. Syst. Sci. 54(2): 255-262 (1997) |
| 161 | | Maxime Crochemore,
Zvi Galil,
Leszek Gasieniec,
Kunsoo Park,
Wojciech Rytter:
Constant-Time Randomized Parallel String Matching.
SIAM J. Comput. 26(4): 950-960 (1997) |
| 1996 |
|---|
| 160 | | David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
Thomas H. Spencer:
Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees.
J. Comput. Syst. Sci. 52(1): 3-27 (1996) |
| 159 | | Zvi Galil,
Kunsoo Park:
Alphabet-Independent Two-Dimensional Witness Computation.
SIAM J. Comput. 25(5): 907-935 (1996) |
| 1995 |
|---|
| 158 | | Zvi Galil,
Esko Ukkonen:
Combinatorial Pattern Matching, 6th Annual Symposium, CPM 95, Espoo, Finland, July 5-7, 1995, Proceedings
Springer 1995 |
| 157 | | Noga Alon,
Zvi Galil,
Moti Yung:
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.
ESA 1995: 523-537 |
| 156 | | Zvi Galil,
Alain J. Mayer,
Moti Yung:
Resolving Message Complexity of Byzantine Agreement and beyond.
FOCS 1995: 724-733 |
| 155 | | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds on Algebraic Random Access Machines (Extended Abstract).
ICALP 1995: 360-371 |
| 154 | | Pavol Duris,
Zvi Galil:
Sensing Versus Nonsensing Automata.
ICALP 1995: 455-463 |
| 153 | EE | Zvi Galil,
Xiangdong Yu:
Short length versions of Menger's theorem (Extended Abstract).
STOC 1995: 499-508 |
| 152 | EE | Artur Czumaj,
Zvi Galil,
Leszek Gasieniec,
Kunsoo Park,
Wojciech Plandowski:
Work-time-optimal parallel algorithms for string problems.
STOC 1995: 713-722 |
| 151 | | Dany Breslauer,
Zvi Galil:
Finding All Periods and Initial Palindromes of a String in Parallel.
Algorithmica 14(4): 355-366 (1995) |
| 150 | EE | Amir M. Ben-Amram,
Zvi Galil:
On Data Structure Tradeoffs and an Application to Union-Find
Electronic Colloquium on Computational Complexity (ECCC) 2(62): (1995) |
| 149 | | Amir M. Ben-Amram,
Zvi Galil:
On the Power of the Shift Instruction
Inf. Comput. 117(1): 19-36 (1995) |
| 148 | EE | Zvi Galil:
A Constant-Time Optimal Parallel String-Matching Algorithm.
J. ACM 42(4): 908-918 (1995) |
| 147 | EE | Alberto Apostolico,
Dany Breslauer,
Zvi Galil:
Parallel Detection of all Palindromes in a String.
Theor. Comput. Sci. 141(1&2): 163-173 (1995) |
| 1994 |
|---|
| 146 | | Alberto Apostolico,
Dany Breslauer,
Zvi Galil:
Parallel Detection of all Palindromes in a String.
STACS 1994: 497-506 |
| 145 | EE | Moshe Dubiner,
Zvi Galil,
Edith Magen:
Faster Tree Pattern Matching.
J. ACM 41(2): 205-213 (1994) |
| 144 | | Amihood Amir,
Martin Farach,
Zvi Galil,
Raffaele Giancarlo,
Kunsoo Park:
Dynamic Dictionary Matching.
J. Comput. Syst. Sci. 49(2): 208-222 (1994) |
| 143 | | Zvi Galil,
Kunsoo Park:
Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency.
J. Parallel Distrib. Comput. 21(2): 213-222 (1994) |
| 1993 |
|---|
| 142 | | Alberto Apostolico,
Maxime Crochemore,
Zvi Galil,
Udi Manber:
Combinatorial Pattern Matching, 4th Annual Symposium, CPM 93, Padova, Italy, June 2-4, 1993, Proceedings
Springer 1993 |
| 141 | | Richard Cole,
Maxime Crochemore,
Zvi Galil,
Leszek Gasieniec,
Ramesh Hariharan,
S. Muthukrishnan,
Kunsoo Park,
Wojciech Rytter:
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
FOCS 1993: 248-258 |
| 140 | | Amir M. Ben-Amram,
Zvi Galil:
When can we sort in o(n log n) time?
FOCS 1993: 538-546 |
| 139 | | Matthew K. Franklin,
Zvi Galil,
Moti Yung:
Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems
FOCS 1993: 670-679 |
| 138 | EE | David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
Thomas H. Spencer:
Separator based sparsification for dynamic planar graph algorithms.
STOC 1993: 208-217 |
| 137 | | Pavol Duris,
Zvi Galil:
On the Power of Multiple Reads in a Chip
Inf. Comput. 104(2): 277-287 (1993) |
| 136 | EE | Zvi Galil,
Oded Margalit:
Witnesses for Boolean Matrix Multiplication and for Transitive Closure.
J. Complexity 9(2): 201-221 (1993) |
| 135 | EE | Dany Breslauer,
Zvi Galil:
Efficient Comparison Based String Matching.
J. Complexity 9(3): 339-365 (1993) |
| 134 | | Zvi Galil,
Giuseppe F. Italiano:
Maintaining the 3-Edge-Connected Components of a Graph On-Line.
SIAM J. Comput. 22(1): 11-28 (1993) |
| 1992 |
|---|
| 133 | | Danny Dolev,
Zvi Galil,
Michael Rodeh:
Theory of Computing and Systems, ISTCS'92, Israel Symposium, Haifa, Israel, May 1992
Springer 1992 |
| 132 | | Alberto Apostolico,
Maxime Crochemore,
Zvi Galil,
Udi Manber:
Combinatorial Pattern Matching, Third Annual Symposium, CPM 92, Tucson, Arizona, USA, April 29 - May 1, 1992, Proceedings
Springer 1992 |
| 131 | | Zvi Galil,
Kunsoo Park:
Truly Alphabet-Independent Two-Dimensional Pattern Matching
FOCS 1992: 247-256 |
| 130 | | Noga Alon,
Zvi Galil,
Oded Margalit,
Moni Naor:
Witnesses for Boolean Matrix Multiplication and for Shortest Paths
FOCS 1992: 417-426 |
| 129 | | David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
Amnon Nissenzweig:
Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)
FOCS 1992: 60-69 |
| 128 | | Alberto Apostolico,
Dany Breslauer,
Zvi Galil:
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract).
ICALP 1992: 296-307 |
| 127 | | Zvi Galil,
Giuseppe F. Italiano,
Neil Sarnak:
Fully Dynamic Planarity Testing (Extended Abstract)
STOC 1992: 495-506 |
| 126 | | Zvi Galil:
A Constant-Time Optimal Parallel String-Matching Algorithm
STOC 1992: 69-76 |
| 125 | EE | David Eppstein,
Zvi Galil,
Raffaele Giancarlo,
Giuseppe F. Italiano:
Sparse Dynamic Programming I: Linear Cost Functions.
J. ACM 39(3): 519-545 (1992) |
| 124 | EE | David Eppstein,
Zvi Galil,
Raffaele Giancarlo,
Giuseppe F. Italiano:
Sparse Dynamic Programming II: Convex and Concave Cost Functions.
J. ACM 39(3): 546-567 (1992) |
| 123 | EE | Amir M. Ben-Amram,
Zvi Galil:
On Pointers versus Addresses.
J. ACM 39(3): 617-648 (1992) |
| 122 | | Zvi Galil,
Raffaele Giancarlo:
On the Exact Complexity of String Matching: Upper Bounds.
SIAM J. Comput. 21(3): 407-437 (1992) |
| 121 | | Dany Breslauer,
Zvi Galil:
A Lower Bound for Parallel String Matching.
SIAM J. Comput. 21(5): 856-862 (1992) |
| 120 | | Zvi Galil,
Giuseppe F. Italiano:
Fully Dynamic Algorithms for 2-Edge Connectivity.
SIAM J. Comput. 21(6): 1047-1069 (1992) |
| 119 | | Zvi Galil,
Kunsoo Park:
Dynamic Programming with Convexity, Concavity, and Sparsity.
Theor. Comput. Sci. 92(1): 49-76 (1992) |
| 118 | | Yuval Rabani,
Zvi Galil:
On the Space Complexity of Some Algorithms for Sequence Comparison.
Theor. Comput. Sci. 95(2): 231-244 (1992) |
| 1991 |
|---|
| 117 | | Noga Alon,
Zvi Galil,
Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem
FOCS 1991: 569-575 |
| 116 | | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
FOCS 1991: 622-631 |
| 115 | | Zvi Galil,
Giuseppe F. Italiano:
Maintaining Biconnected Components of Dynamic Planar Graphs.
ICALP 1991: 339-350 |
| 114 | | Pavol Duris,
Zvi Galil:
On the Power of Multiple Reads in a Chip.
ICALP 1991: 697-706 |
| 113 | | Zvi Galil,
Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.
ICALP 1991: 719-727 |
| 112 | | Zvi Galil,
Giuseppe F. Italiano:
Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract)
STOC 1991: 317-327 |
| 111 | | Dany Breslauer,
Zvi Galil:
A Lower Bound for Parallel String Matching
STOC 1991: 439-443 |
| 110 | | Zvi Galil,
Giuseppe F. Italiano:
Data Structures and Algorithms for Disjoint Set Union Problems.
ACM Comput. Surv. 23(3): 319-344 (1991) |
| 109 | | Zvi Galil,
Giuseppe F. Italiano:
A Note on Set Union with Arbitrary Deunions.
Inf. Process. Lett. 37(6): 331-335 (1991) |
| 108 | | Pavol Duris,
Zvi Galil:
Two Lower Bounds in Asynchronous Distributed Computation.
J. Comput. Syst. Sci. 42(3): 254-266 (1991) |
| 107 | | Zvi Galil,
Raffaele Giancarlo:
On the Exact Complexity of String Matching: Lower Bounds.
SIAM J. Comput. 20(6): 1008-1020 (1991) |
| 106 | | Zvi Galil,
Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.
SIAM J. Comput. 20(6): 1157-1189 (1991) |
| 105 | | Amir Averbuch,
Zvi Galil,
Shmuel Winograd:
Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial. Part II: The Algebra G[u]/<u^n>.
Theor. Comput. Sci. 86(2): 143-203 (1991) |
| 1990 |
|---|
| 104 | | Livio Colussi,
Zvi Galil,
Raffaele Giancarlo:
On the Exact Complexity of String Matching (Extended Abstract)
FOCS 1990: 135-144 |
| 103 | | Moshe Dubiner,
Zvi Galil,
Edith Magen:
Faster Tree Pattern Matching
FOCS 1990: 145-150 |
| 102 | | Zvi Galil:
Recent Progress in String Algorithms.
SIGAL International Symposium on Algorithms 1990: 1 |
| 101 | | David Eppstein,
Zvi Galil,
Raffaele Giancarlo,
Giuseppe F. Italiano:
Sparse Dynamic Programming.
SODA 1990: 513-522 |
| 100 | | Zvi Galil,
Kunsoo Park:
A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.
Inf. Process. Lett. 33(6): 309-311 (1990) |
| 99 | | Dany Breslauer,
Zvi Galil:
An Optimal O(log log n) Time Parallel String Matching Algorithm.
SIAM J. Comput. 19(6): 1051-1058 (1990) |
| 98 | | Zvi Galil,
Kunsoo Park:
An Improved Algorithm for Approximate String Matching.
SIAM J. Comput. 19(6): 989-999 (1990) |
| 1989 |
|---|
| 97 | EE | Zvi Galil,
Stuart Haber,
Moti Yung:
A Secure Public-key Authentication Scheme.
EUROCRYPT 1989: 3-15 |
| 96 | | David Eppstein,
Zvi Galil:
Parallel Algorithmic Techniques for Combinatorial Computation.
ICALP 1989: 304-318 |
| 95 | | Zvi Galil,
Kunsoo Park:
An Improved Algorithm for Approximate String Matching.
ICALP 1989: 394-404 |
| 94 | | Omer Berkman,
Dany Breslauer,
Zvi Galil,
Baruch Schieber,
Uzi Vishkin:
Highly Parallelizable Problems (Extended Abstract)
STOC 1989: 309-319 |
| 93 | | Zvi Galil,
Ravi Kannan,
Endre Szemerédi:
On 3-pushdown graphs with large separators.
Combinatorica 9(1): 9-19 (1989) |
| 92 | | Zvi Galil,
Victor Y. Pan:
Parallel Evaluation of the Determinant and of the Inverse of a Matrix.
Inf. Process. Lett. 30(1): 41-45 (1989) |
| 91 | EE | Harold N. Gabow,
Zvi Galil,
Thomas H. Spencer:
Efficient implementation of graph algorithms using contraction.
J. ACM 36(3): 540-572 (1989) |
| 90 | EE | Mark Chaimovich,
Gregory Freiman,
Zvi Galil:
Solving dense subset-sum problems by using analytical number theory.
J. Complexity 5(3): 271-282 (1989) |
| 89 | | Zvi Galil,
Ravi Kannan,
Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines.
J. Comput. Syst. Sci. 38(1): 134-149 (1989) |
| 88 | | Zvi Galil,
Stuart Haber,
Moti Yung:
Minimum-Knowledge Interactive Proofs for Decision Problems.
SIAM J. Comput. 18(4): 711-739 (1989) |
| 87 | | Zvi Galil,
Raffaele Giancarlo:
Speeding up Dynamic Programming with Applications to Molecular Biology.
Theor. Comput. Sci. 64(1): 107-118 (1989) |
| 1988 |
|---|
| 86 | | David Eppstein,
Zvi Galil,
Raffaele Giancarlo:
Speeding up Dynamic Programming
FOCS 1988: 488-496 |
| 85 | | Amir M. Ben-Amram,
Zvi Galil:
On Pointers versus Addresses (Extended Abstract)
FOCS 1988: 532-538 |
| 84 | | Zvi Galil,
Victor Y. Pan:
Improved processor bounds for combinatorial problems in RNC.
Combinatorica 8(2): 189-200 (1988) |
| 83 | EE | Zvi Galil,
Baruch Schieber:
On finding most uniform spanning trees.
Discrete Applied Mathematics 20(2): 173-175 (1988) |
| 82 | EE | Zvi Galil,
Éva Tardos:
An O(n²(m + n log n)log n) min-cost flow algorithm.
J. ACM 35(2): 374-386 (1988) |
| 81 | EE | Zvi Galil,
Raffaele Giancarlo:
Data structures and algorithms for approximate string matching.
J. Complexity 4(1): 33-72 (1988) |
| 80 | | Amir Averbuch,
Zvi Galil,
Shmuel Winograd:
Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial, Part I: The Algeabra G[u] / < Q(u)^l >, l > 1.
Theor. Comput. Sci. 58: 17-56 (1988) |
| 1987 |
|---|
| 79 | EE | Zvi Galil,
Stuart Haber,
Moti Yung:
Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model.
CRYPTO 1987: 135-155 |
| 78 | | Pavol Duris,
Zvi Galil:
Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)
FOCS 1987: 326-330 |
| 77 | | Pavol Duris,
Zvi Galil,
Georg Schnitger:
Lower Bounds on Communication Complexity
Inf. Comput. 73(1): 1-22 (1987) |
| 76 | | Zvi Galil,
Moti Yung:
Partitioned Encryption and Achieving Simultaneity by Partitioning.
Inf. Process. Lett. 26(2): 81-88 (1987) |
| 75 | EE | Zvi Galil,
Christoph M. Hoffmann,
Eugene M. Luks,
Claus-Peter Schnorr,
Andreas Weber:
An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs.
J. ACM 34(3): 513-531 (1987) |
| 74 | | Noga Alon,
Zvi Galil,
V. D. Milman:
Better Expanders and Superconcentrators.
J. Algorithms 8(3): 337-347 (1987) |
| 73 | | Zvi Galil,
Gad M. Landau,
Mordechai M. Yung:
Distributed Algorithms in Synchronous Broadcasting Networks.
Theor. Comput. Sci. 49: 171-184 (1987) |
| 72 | | Zvi Galil,
Raffaele Giancarlo:
Parallel String Matching with k Mismatches.
Theor. Comput. Sci. 51: 341-348 (1987) |
| 1986 |
|---|
| 71 | | Zvi Galil,
Éva Tardos:
An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm
FOCS 1986: 1-9 |
| 70 | | Amir Averbuch,
Shmuel Winograd,
Zvi Galil:
Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial.
ICALP 1986: 31-39 |
| 69 | | Zvi Galil,
Ravi Kannan,
Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines
STOC 1986: 39-49 |
| 68 | EE | Zvi Galil:
Efficient Algorithms for Finding Maximum Matching in Graphs.
ACM Comput. Surv. 18(1): 23-38 (1986) |
| 67 | | Harold N. Gabow,
Zvi Galil,
Thomas H. Spencer,
Robert Endre Tarjan:
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.
Combinatorica 6(2): 109-122 (1986) |
| 66 | | Zvi Galil,
Silvio Micali,
Harold N. Gabow:
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs.
SIAM J. Comput. 15(1): 120-130 (1986) |
| 1985 |
|---|
| 65 | EE | Zvi Galil,
Stuart Haber,
Moti Yung:
Symmetric Public-Key Encryption.
CRYPTO 1985: 128-137 |
| 64 | | Zvi Galil,
Stuart Haber,
Moti Yung:
A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract)
FOCS 1985: 360-371 |
| 63 | | Zvi Galil,
Victor Y. Pan:
Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC
FOCS 1985: 490-495 |
| 62 | | Gad M. Landau,
Mordechai M. Yung,
Zvi Galil:
Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract).
ICALP 1985: 363-372 |
| 61 | | Zvi Galil:
Optimal Parallel Algorithms for String Matching
Information and Control 67(1-3): 144-157 (1985) |
| 1984 |
|---|
| 60 | | Harold N. Gabow,
Zvi Galil,
Thomas H. Spencer:
Efficient Implementation of Graph Algorithms Using Contraction
FOCS 1984: 347-357 |
| 59 | | Zvi Galil:
Optimal Parallel Algorithms for String Matching
STOC 1984: 240-248 |
| 58 | | Pavol Duris,
Zvi Galil,
Georg Schnitger:
Lower Bounds on Communication Complexity
STOC 1984: 81-91 |
| 57 | | Pavol Duris,
Zvi Galil,
Wolfgang J. Paul,
Rüdiger Reischuk:
Two Nonlinear Lower Bounds for On-Line Computations
Information and Control 60(1-3): 1-11 (1984) |
| 56 | | Pavol Duris,
Zvi Galil:
A Time-Space Tradeoff for Language Recognition.
Mathematical Systems Theory 17(1): 3-12 (1984) |
| 55 | | Pavol Duris,
Zvi Galil:
Two Tapes are Better than One for Nondeterministic Machines.
SIAM J. Comput. 13(2): 219-227 (1984) |
| 1983 |
|---|
| 54 | | Zvi Galil:
Efficient Algorithms for Finding Maximal Matching in Graphs.
CAAP 1983: 90-113 |
| 53 | | Pavol Duris,
Zvi Galil,
Wolfgang J. Paul,
Rüdiger Reischuk:
Two Nonlinear Lower Bounds
STOC 1983: 127-132 |
| 52 | EE | Zvi Galil,
Wolfgang J. Paul:
An Efficient General-Purpose Parallel Computer
J. ACM 30(2): 360-387 (1983) |
| 51 | | Daniel Leven,
Zvi Galil:
NP Completeness of Finding the Chromatic Index of Regular Graphs.
J. Algorithms 4(1): 35-44 (1983) |
| 50 | | Zvi Galil,
Joel I. Seiferas:
Time-Space-Optimal String Matching.
J. Comput. Syst. Sci. 26(3): 280-294 (1983) |
| 1982 |
|---|
| 49 | | Zvi Galil,
Christoph M. Hoffmann,
Eugene M. Luks,
Claus-Peter Schnorr,
Andreas Weber:
An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs
FOCS 1982: 118-125 |
| 48 | | Zvi Galil,
Silvio Micali,
Harold N. Gabow:
Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
FOCS 1982: 255-261 |
| 47 | | Pavol Duris,
Zvi Galil:
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store.
ICALP 1982: 166-175 |
| 46 | | Pavol Duris,
Zvi Galil:
Two Tapes are Better than One for Nondeterministic Machines
STOC 1982: 1-7 |
| 45 | | Albert G. Greenberg,
Richard E. Ladner,
Mike Paterson,
Zvi Galil:
Efficient Parallel Algorithms for Linear Recurrence Computation.
Inf. Process. Lett. 15(1): 31-35 (1982) |
| 44 | | Pavol Duris,
Zvi Galil:
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store
Information and Control 54(3): 217-227 (1982) |
| 43 | EE | Zvi Galil:
An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database.
J. ACM 29(1): 96-102 (1982) |
| 42 | | Pavol Duris,
Zvi Galil:
Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines.
Theor. Comput. Sci. 21: 39-53 (1982) |
| 1981 |
|---|
| 41 | | Pavol Duris,
Zvi Galil:
A Time-Space Tradeoff for Language Recognition
FOCS 1981: 53-57 |
| 40 | | Zvi Galil,
Joel I. Seiferas:
Time-Space-Optimal String Matching
STOC 1981: 106-113 |
| 39 | | Pavol Duris,
Zvi Galil:
Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)
STOC 1981: 177-188 |
| 38 | | Zvi Galil,
Wolfgang J. Paul:
An Efficient General Purpose Parallel Computer
STOC 1981: 247-262 |
| 37 | EE | Zvi Galil:
String Matching in Real Time.
J. ACM 28(1): 134-149 (1981) |
| 36 | | Ofer Gabber,
Zvi Galil:
Explicit Constructions of Linear-Sized Superconcentrators.
J. Comput. Syst. Sci. 22(3): 407-420 (1981) |
| 35 | | Zvi Galil,
Joel I. Seiferas:
Linear-Time String-Matching Using only a Fixed Number of Local Storage Locations.
Theor. Comput. Sci. 13: 331-336 (1981) |
| 34 | | Zvi Galil:
On the Theoretical Efficiency of Various Network Flow Algorithms.
Theor. Comput. Sci. 14: 103-111 (1981) |
| 1980 |
|---|
| 33 | | Zvi Galil,
Wolfgang J. Paul:
Effizienz Paralleler Rechner.
GI Jahrestagung 1980: 54-64 |
| 32 | | Zvi Galil:
An Almost Linaer Time Algorithm for Computing a Dependency Basis in a Relational Data Base.
ICALP 1980: 246-256 |
| 31 | | Zvi Galil:
Applications of Efficient Mergeable Heaps for Optimization Problems on Trees.
Acta Inf. 13: 53-58 (1980) |
| 30 | | Zvi Galil:
An O(V5/3 E2/3) Algorithm for the Maximal Flow Problem.
Acta Inf. 14: 221-242 (1980) |
| 29 | | Zvi Galil,
Amnon Naamad:
An O(EVlog²V) Algorithm for the Maximal Flow Problem.
J. Comput. Syst. Sci. 21(2): 203-217 (1980) |
| 28 | | Zvi Galil:
Finding the Vertex Connectivity of Graphs.
SIAM J. Comput. 9(1): 197-199 (1980) |
| 27 | | Zvi Galil,
Joel I. Seiferas:
Saving Space in Fast String-Matching.
SIAM J. Comput. 9(2): 417-438 (1980) |
| 1979 |
|---|
| 26 | | Ofer Gabber,
Zvi Galil:
Explicit Constructions of Linear Size Superconcentrators
FOCS 1979: 364-370 |
| 25 | | Zvi Galil,
Amnon Naamad:
Network Flow and Generalized Path Compression
STOC 1979: 13-26 |
| 24 | | Arnold L. Rosenberg,
Derick Wood,
Zvi Galil:
Storage Representations for Tree-Like Data Structures
STOC 1979: 99-107 |
| 23 | | Zvi Galil:
On Improving the Worse Case Running Time of the Boyer-Moore String Matching Algorithm.
Commun. ACM 22(9): 505-508 (1979) |
| 22 | EE | Zvi Galil,
Nimrod Megiddo:
A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort.
J. ACM 26(1): 58-64 (1979) |
| 21 | | Arnold L. Rosenberg,
Derick Wood,
Zvi Galil:
Storage Representations for Tree-Like Data Structures.
Mathematical Systems Theory 13: 105-130 (1979) |
| 1978 |
|---|
| 20 | | Zvi Galil:
A New Algorithm for the Maximal Flow Problem
FOCS 1978: 231-245 |
| 19 | | Zvi Galil:
On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm.
ICALP 1978: 241-250 |
| 18 | EE | Zvi Galil,
Joel I. Seiferas:
A Linear-Time On-Line Recognition Algorithm for ``Palstar''.
J. ACM 25(1): 102-111 (1978) |
| 17 | | Zvi Galil:
Palindrome Recognition in Real Time by a Multitape Turing Machine.
J. Comput. Syst. Sci. 16(2): 140-157 (1978) |
| 1977 |
|---|
| 16 | | Zvi Galil,
Joel I. Seiferas:
Saving Space in Fast String-Matching
FOCS 1977: 179-188 |
| 15 | | Zvi Galil:
Some Open Problems in the Theory of Computation as Questions about Two-Way Deterministic Pushdown Automaton Languages.
Mathematical Systems Theory 10: 211-228 (1977) |
| 14 | | Joel I. Seiferas,
Zvi Galil:
Real-Time Recognition of Substring Repetition and Reversal.
Mathematical Systems Theory 11: 111-146 (1977) |
| 13 | | Zvi Galil:
On Resolution with Clauses of Bounded Size.
SIAM J. Comput. 6(3): 444-459 (1977) |
| 12 | | Zvi Galil:
On the Complexity of Regular Resolution and the Davis-Putnam Procedure.
Theor. Comput. Sci. 4(1): 23-46 (1977) |
| 11 | | Zvi Galil,
Nimrod Megiddo:
Cyclic Ordering is NP-Complete.
Theor. Comput. Sci. 5(2): 179-182 (1977) |
| 1976 |
|---|
| 10 | | Zvi Galil,
Joel I. Seiferas:
Recognizing Certain Repetitions and Reversals Within Strings
FOCS 1976: 236-252 |
| 9 | | Zvi Galil:
On Enumeration Procedures for Theorem Proving and for Integer Programming.
ICALP 1976: 355-381 |
| 8 | | Zvi Galil:
Real-Time Algorithms for String-Matching and Palindrome Recognition
STOC 1976: 161-173 |
| 7 | | Zvi Galil:
Hierarchies of Complete Problems.
Acta Inf. 6: 77-88 (1976) |
| 6 | | Zvi Galil:
Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms.
Inf. Process. Lett. 4(4): 85-87 (1976) |
| 5 | | Zvi Galil,
Janos Simon:
A Note on Multiple-Entry Finite Automata.
J. Comput. Syst. Sci. 12(3): 350-351 (1976) |
| 1975 |
|---|
| 4 | | Kurt Mehlhorn,
Zvi Galil:
Monotone Switching Circuits and Boolean Matrix Product.
MFCS 1975: 315-319 |
| 3 | | Zvi Galil:
On the Validity and Complexity of Bounded Resolution
STOC 1975: 72-82 |
| 2 | | Zvi Galil:
Functional Schemas with Nested Predicates
Information and Control 27(4): 349-368 (1975) |
| 1974 |
|---|
| 1 | | Zvi Galil:
Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation
FOCS 1974: 170-177 |
