Udi Manber  All Publications
Books

Introduction to Algorithms  A Creative Approach,
AddisonWesley, Reading, MA, April 1989 (eleventh printing, 1994).

Computer Science: Research and Applications,
Plenum Press, New York, 1992
(edited joinly with R. BaezaYates).

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

Combinatorial Pattern Matching 1993,
Lecture Notes in Computer Science #684,
SpringerVerlag, 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,
C29 (October 1980), pp. 934937.

U. Manber and M. Tompa,
``The Effect of Number of Hamiltonian Paths on the Complexity of a VertexColoring Problem,"
SIAM Journal on Computing,
13 (February 1984), pp. 109115.
An earlier version appeared in
22nd Annual Symposium on Foundations of Computer Science,
(October 1981), pp. 220227.

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

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

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

U. Manber,
``Concurrent Maintenance of Binary Search Trees,"
IEEE Transactions on Software Engineering,
SE10 (November 1984), pp. 777784.

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

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

M. Livny and U. Manber,
``Distributed Computation via Active Messages,"
IEEE Transactions on Computers,
C34 (December 1985), pp. 11851190.

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

A. Greenberg and U. Manber,
``A Probabilistic Pipeline Algorithm for KSelection on the Tree Machine,"
IEEE Transactions on Computers,
C36 (March 1987), pp. 359362.
An earlier version appeared in
1985 International Conference on Parallel Processing,
Chicago (August 1985), pp. 15.

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

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

S.W. Bent and U. Manber,
``On NonIntersecting Eulerian Circuits,"
Discrete Applied Mathematics,
18 (1987), pp. 8794.

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

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

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

U. Manber,
``Recognizing BreadthFirst Search Trees in Linear Time,"
Information Processing Letters,
34 (1990), pp. 167171.

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

U. Manber
``Chain Reactions in Networks,"
Computer,
23 (October 1990), pp. 5763.

U. Manber and R. BaezaYates,
``An Algorithm for String Matching With a Sequence of Don't Cares,"
Information Processing Letters,
37 (February 1991), pp. 133136.

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

S. Wu and U. Manber,
``PathMatching Problems,"
Algorithmica 8 (July 1992), pp. 89101.

S. Wu and U. Manber,
``An Algorithm for MinCost EdgeDisjoint Cycles And Its Applications,"
Operations Research Letters
12 (September 1992), pp. 173178.

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

U. Manber and E. W. Myers,
``Suffix Arrays: A New Method for OnLine String Searches,"
SIAM Journal on Computing,
(October 1993), pp. 935948.
An earlier version appeared in the
first Annual ACMSIAM Symposium on Discrete Algorithms,
San Francisco (January 1990), pp. 319327.

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

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. 98107.

S. Wu, U. Manber, and R. E. W. Myers,
``A SubQuadratic Algorithm for
Approximate Regular Expression Matching,''
Journal of Algorithms
19 (1995), pp. 346360.

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. 119125.
An earlier version appeared in the
Proceedings of the Second International World Wide Web Conference,
Chicago, Illinois
(October 1994),
pp. 763771.

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

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

U. Manber,
``A Simple Scheme to Make Passwords Based on OneWay Functions
Much Harder to Crack,''
Computers & Security
15 (2) (1996), pp. 171176.

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. 124136.
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. 113124.
Refereed conferences

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

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. 367369.

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. 7481.

M. Vernon and U. Manber,
``Distributed FirstCome FirstServed and RoundRobin Protocols and Their Application to Multiprocessor Bus Arbitration,"
15th Annual International Symposium on Computer Architecture,
Honolulu (May 1988), pp. 269277.

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

S. Wu and U. Manber,
``Agrep  A Fast Approximate PatternMatching Tool,"
Usenix Winter 1992 Technical Conference,
San Francisco (January 1992), pp. 153162.

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. 2233.

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

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

R. BaezaYates, W. Cunto, U. Manber, and S. Wu,
``Proximity Matching Using FixedQueries Trees,''
The Fifth Combinatorial Pattern Matching Symp.,
M. Crochemore and D. Gusfield, Ed.,
Springer Verlag Lecture Notes in Computer Science #807
(June 1994) pp. 198212.

P. Klark, and U. Manber,
``Developing a Personal Internet Assistant,''
Proceedings of EDMedia 95, World Conf. on Multimedia and Hypermedia,
Graz, Austria (June 1995), pp. 372377.

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

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

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

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

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

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

U. Manber,
a foreword to
Information Retrieval: Data Structures and Algorithms,
by B. Frakes and R. BaezaYates, PrenticeHall, 1992.

U. Manber and S. Wu,
``Approximate Pattern Matching,"
BYTE Magazine (November 1992), pp. 281292.

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. 213215.

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

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