Udi Manber -- All Publications

Books

• Introduction to Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, April 1989 (eleventh printing, 1994).

• Computer Science: Research and Applications, Plenum Press, New York, 1992 (edited joinly with R. Baeza-Yates).

• Combinatorial Pattern Matching 1992, Lecture Notes in Computer Science #644, Springer-Verlag, Berlin, Germany, 1992 (edited jointly with A. Apostolico, M. Crochemore, and Z. Galil).

• Combinatorial Pattern Matching 1993, Lecture Notes in Computer Science #684, Springer-Verlag, Berlin, Germany, 1993 (edited jointly with A. Apostolico, M. Crochemore, and Z. Galil).

Refereed journals

• U. Manber, ``System Diagnosis With Repair," IEEE Transactions on Computers, C-29 (October 1980), pp. 934-937.

• U. Manber and M. Tompa, ``The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem," SIAM Journal on Computing, 13 (February 1984), pp. 109-115. An earlier version appeared in 22nd Annual Symposium on Foundations of Computer Science, (October 1981), pp. 220-227.

• U. Manber and S. Israni, ``Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting," Journal of Manufacturing Systems, 3 (1984), pp. 81-89.

• U. Manber, ``A Probabilistic Lower Bound for Checking Disjointness of Sets," Information Processing Letters 19 (July 1984), pp. 51-53.

• U. Manber and R.E. Ladner, ``Concurrency Control in a Dynamic Search Structure," ACM Transactions on Database Systems, 9 (September 1984), pp. 439-455. An earlier version appeared in the first Annual ACM Symposium on Principles of Database Systems, Los Angeles (March 1982), pp. 268-282.

• U. Manber, ``Concurrent Maintenance of Binary Search Trees," IEEE Transactions on Software Engineering, SE-10 (November 1984), pp. 777-784.

• U. Manber and M. Tompa, ``The Complexity of Problems on Probabilistic, Nondeterministic, and Alternating Decision Trees," Journal of the ACM, 32 (July 1985), pp. 720-732. An earlier version appeared in 14th Annual ACM Symposium on Theory of Computing, San Francisco (May 1982), pp. 234-244.

• S. Moran, M. Snir, and U. Manber, ``Applications of Ramsey's Theorem to Decision Trees Complexity," Journal of the ACM, 32 (October 1985), pp. 938-949. An earlier version appeared in 25th Annual Symposium on Foundations of Computer Science, Singer Island (October 1984), pp. 332-337.

• M. Livny and U. Manber, ``Distributed Computation via Active Messages," IEEE Transactions on Computers, C-34 (December 1985), pp. 1185-1190.

• U. Manber, ``On Maintaining Dynamic Information in a Concurrent Environment," SIAM Journal on Computing, 15 (November 1986), pp. 1130-1142. An earlier version appeared in 16th Annual ACM Symposium on Theory of Computing, Washington DC (April 1984), pp. 273-278.

• A. Greenberg and U. Manber, ``A Probabilistic Pipeline Algorithm for K-Selection on the Tree Machine," IEEE Transactions on Computers, C-36 (March 1987), pp. 359-362. An earlier version appeared in 1985 International Conference on Parallel Processing, Chicago (August 1985), pp. 1-5.

• R.A. Finkel and U. Manber, ``DIB -- A Distributed Implementation of Backtracking," ACM Transactions on Programming Languages and Systems, 9 (April 1987), pp. 235-256. An earlier version appeared in The Fifth International Conference on Distributed Computing Systems, Denver (May 1985), pp. 446-452.

• T. Kurtz and U. Manber, ``A Probabilistic Distributed Algorithm for Set Intersection and its Analysis," Theoretical Computer Science, 49 (1987), pp. 267-282. An earlier version appeared in 12th International Colloquium on Automata, Languages, and Programming, Nafplion, Greece (July 1985), pp. 356-362.

• S.W. Bent and U. Manber, ``On Non-Intersecting Eulerian Circuits," Discrete Applied Mathematics, 18 (1987), pp. 87-94.

• U. Manber and L. McVoy, ``Efficient Storage of Nonadaptive Routing Tables," Networks, 18 (1988), pp. 263-272.

• U. Manber, ``Using Induction to Design Algorithms," Communications of the ACM, 31 (November 1988), pp. 1300-1313.

• D. Hensgen, R. Finkel, and U. Manber, ``Two Algorithms for Barrier Synchronization," International Journal of Parallel Programming, 17 (1988), pp. 1-17.

• U. Manber, ``Recognizing Breadth-First Search Trees in Linear Time," Information Processing Letters, 34 (1990), pp. 167-171.

• S. Wu, U. Manber, E. W. Myers, and W. Miller, ``An O(NP) Sequence Comparison Algorithm," Information Processing Letters, 35 (1990), pp. 317-323.

• U. Manber ``Chain Reactions in Networks," Computer, 23 (October 1990), pp. 57-63.

• U. Manber and R. Baeza-Yates, ``An Algorithm for String Matching With a Sequence of Don't Cares," Information Processing Letters, 37 (February 1991), pp. 133-136.

• K. Pruhs and U. Manber, ``The Complexity of Controlled Selection," Information and Computation, 91 (March 1991), pp. 103-127. An earlier version appeared in 16th International Colloquium on Automata, Languages, and Programming, Stresa, Italy (July 1989), pp. 672-686.

• S. Wu and U. Manber, ``Path-Matching Problems," Algorithmica 8 (July 1992), pp. 89-101.

• S. Wu and U. Manber, ``An Algorithm for Min-Cost Edge-Disjoint Cycles And Its Applications," Operations Research Letters 12 (September 1992), pp. 173-178.

• S. Wu and U. Manber, ``Fast Text Searching Allowing Errors," Communications of the ACM 35 (October 1992), pp. 83-91.

• U. Manber and E. W. Myers, ``Suffix Arrays: A New Method for On-Line String Searches," SIAM Journal on Computing, (October 1993), pp. 935-948. An earlier version appeared in the first Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco (January 1990), pp. 319-327.

• U. Manber and S. Wu, ``An Algorithm for Approximate Membership Checking With Application to Password Security,'' Information Processing Letters 50 (May 1994), pp. 191-197.

• C. M. Bowman, P. B. Danzig, U. Manber, and M. F. Schwartz, ``Scalable Internet Resource Discovery: Research Problems and Approaches,'' Communication of the ACM 37 (August 1994), pp. 98-107.

• S. Wu, U. Manber, and R. E. W. Myers, ``A Sub-Quadratic Algorithm for Approximate Regular Expression Matching,'' Journal of Algorithms 19 (1995), pp. 346-360.

• C. M. Bowman, P. B. Danzig, D. R. Hardy, U. Manber, and M. F. Schwartz, ``The Harvest Information Discovery and Access System," Computer Networks and ISDN Systems 28 (1995) pp. 119-125. An earlier version appeared in the Proceedings of the Second International World Wide Web Conference, Chicago, Illinois (October 1994), pp. 763-771.

• S. Wu, U. Manber, and E. W. Myers, ``A Subquadratic Algorithm for Approximate Limited Expression Matching," Algorithmica 15 (January 1996), pp. 50-67.

• E. Weinberger and U. Manber, ``Efficient Searching for Specific Resources on the World-Wide Web: Creation of a Search Server for Radiologists,'' American Journal of Roentgenology, 166 (1996), pp. 1265-1267.

• U. Manber, ``A Simple Scheme to Make Passwords Based on One-Way Functions Much Harder to Crack,'' Computers & Security 15 (2) (1996), pp. 171-176.

• U. Manber, ``A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File,'' ACM Trans. on Information Systems, 15 (2) (April 1997), pp. 124-136. An earlier version appeared in The Fifth Combinatorial Pattern Matching Symp., M. Crochemore and D. Gusfield, Ed., Springer Verlag Lecture Notes in Computer Science #807 (June 1994) pp. 113-124.

Refereed conferences

• M. Livny and U. Manber, ``Shift Arithmetic on a Token Ring Network," 1985 International Conference on Parallel Processing, Chicago (August 1985), pp. 301-304.

• J. D. Parker and U. Manber, ``The Sibling Trie: A Highly Concurrent Search Structure," 24th annual Allerton Conference on Communication, Control, and Computing, Illinois (October 1986).

• M. Livny and U. Manber, ``Active Channels and Their Applications to Parallel Computing," 1987 International Conference on Parallel Processing, Chicago (August 1987), pp. 367-369.

• N. Alon, A. Barak, and U. Manber, ``On Disseminating Information Reliably Without Broadcasting," the 7th International Conference on Distributed Computing Systems, Berlin (September 1987), pp. 74-81.

• M. Vernon and U. Manber, ``Distributed First-Come First-Served and Round-Robin Protocols and Their Application to Multiprocessor Bus Arbitration," 15th Annual International Symposium on Computer Architecture, Honolulu (May 1988), pp. 269-277.

• P. Lai and U. Manber, ``Flying through Hypertext," Proc. of the Third ACM Conference on Hypertext, San Antonio, Texas (December 1991), pp. 123-132.

• S. Wu and U. Manber, ``Agrep -- A Fast Approximate Pattern-Matching Tool," Usenix Winter 1992 Technical Conference, San Francisco (January 1992), pp. 153-162.

• U. Manber and S. Wu, ``Approximate String Matching With Arbitrary Costs for Text and Hypertext," Proc. of the IAPR International Workshop on Structural and Syntactic Pattern Recognition, Bern, Switzerland (August 1992), pp. 22-33.

• U. Manber, ``Finding Similar Files in a Large File System," Usenix Winter 1994 Technical Conference, San Francisco (January 1994), pp. 1-10.

• U. Manber and S. Wu, ``GLIMPSE: A Tool to Search Through Entire File Systems," Usenix Winter 1994 Technical Conference, San Francisco (January 1994), pp. 23-32.

• R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu, ``Proximity Matching Using Fixed-Queries Trees,'' The Fifth Combinatorial Pattern Matching Symp., M. Crochemore and D. Gusfield, Ed., Springer Verlag Lecture Notes in Computer Science #807 (June 1994) pp. 198-212.

• P. Klark, and U. Manber, ``Developing a Personal Internet Assistant,'' Proceedings of ED-Media 95, World Conf. on Multimedia and Hypermedia, Graz, Austria (June 1995), pp. 372-377.

• R. Muth, and U. Manber, ``Approximate Multiple String Search,'' the 7th Annual Combinatorial Pattern Matching Symp., Laguna Beach, CA (June 1996), pp. 75-86.

• U. Manber, M. Smith, and B. Gopal, ``WebGlimpse -- Combining Browsing and Searching,'' Usenix 1997 Annual Technical Conference, Anaheim, CA (January 1997), pp. 195-206.

• U. Manber, ``The Use of Customized Emphasis in Text Visualization,'' IEEE International Conf. on Information Visualization IV'97, London, England (August 1997), pp. 132-138.

• U. Manber, and Peter Bigot, ``The Search Broker,'' First Usenix Symp. on Internet Technologies and Systems, Monterey, CA (December 1997), pp. 231-240.

• U. Manber, ``Creating a Personal Web Notebook,'' First Usenix Symp. on Internet Technologies and Systems, Monterey, CA (December 1997), pp. 183-192.

• B. Baker, and U. Manber, ``Deducing Similarities in Java Sources from Bytecodes,'' Usenix 1998 Annual Technical Conference, New Orleans, LA (June 1998), pp. 179-190.

Invited Publications

• U. Manber, a foreword to Information Retrieval: Data Structures and Algorithms, by B. Frakes and R. Baeza-Yates, Prentice-Hall, 1992.

• U. Manber and S. Wu, ``Approximate Pattern Matching," BYTE Magazine (November 1992), pp. 281-292.

• U. Manber, ``Future Directions and Research Problems in the World Wide Web,'' Fifteenth ACM Symposium on Principles of Database Systems (PODS), Montreal, Canada (June 1996), pp. 213-215.

• U. Manber and P.A. Bigot, ``Connecting Diverse Web Search Facilities,'' Bulletin of the Technical Committee on Data Engineering 21 (June 1988), pp. 21-27.

• U. Manber, ``How to find it: Research issues in distributed search.'' Keynote Address, joint PODC and SPAA conferences, June 1998, to appear.

Back to Udi Manber's Home Page