Dan Hirschberg's Publications -- by topic

• Longest Common Subsequence
• Data Compression
• Trees
• Search
• Parallelism
• Breakpoints
• Other

• A linear space algorithm for computing maximal common subsequences. Comm. ACM 18,6 (1975) 341-343.
• Bounds on the complexity of the longest common subsequence problem. (with A.V. Aho and J.D. Ullman) Proc. 15th Annual Symp. on Switching and Automata Theory, New Orleans LA, IEEE (1974) 104-109. Journal ACM 23,1 (1976) 1-12.
• Complexity of common subsequence problems. Fundamentals of Computation Theory, Poznan Poland, Lecture Notes in Computer Science, 56, Springer-Verlag, Berlin (1977) 393-398.
• Algorithms for the longest common subsequence problem. Journal ACM 24,4 (1977) 664-675.
• An information theoretic lower bound for the longest common subsequence problem. Information Processing Letters 7,1 (1978) 40-41.
• Recent results on the complexity of common subsequence problems. Time Warps, String Edits, and Macromolecules, D. Sankoff and J.B. Kruskal, ed., Addison-Wesley, 1983, 323-328.
• The Set LCS problem. (with L.L. Larmore) Algorithmica 2 (1987) 91-95.
• The Set-Set LCS problem. (with L.L. Larmore) Algorithmica 4,4 (1989) 503-510.
• Serial computations of Levenshtein distances. In Pattern Matching Algorithms, A. Apostolico and Z. Galil, eds., Oxford University Press (1997) 123-141.

• Data compression. (with D.A. Lelewer) Computing Surveys 19,3 (1987) 261-297. Reprinted in Japanese BIT Special issue in Computer Science (1989) 165-195. (in HTML)
• Efficient decoding of prefix codes. (with D.A. Lelewer) Comm. ACM 33,4 (1990) 449-459.
• Length-limited coding. (with L.L. Larmore) Proc. First Annual Symposium on Discrete Algorithms, San Francisco, SIAM, Phil. (1990) 310-318.
• A fast algorithm for optimal length-limited codes. (with L.L. Larmore) Journal ACM 37,3 (1990) 464-473.
• An order-2 context model for data compression with reduced time and space requirements. (with D.A. Lelewer) Tech. Rpt. 90-33, ICS Dept., UC Irvine (1990).
• Streamlining context models for data compression. (with D.A. Lelewer) Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1991) 313-322.
• Systolic implementations for transpose coding. (with L.M. Stauffer) Tech. Rpt. 91-69, ICS Dept., UC Irvine (1991).
• Context modeling for text compression. (with D.A. Lelewer) Image and Text Compression, J. A. Storer, ed., Kluwer Academic Publishers, Boston, Mass., 1992, 113-145.
• Transpose coding on the systolic array. (with L.M. Stauffer) Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1992) 162-171.
• Self-organizing lists on the Xnet. (with L.M. Stauffer) Tech. Rpt. 92-81, ICS Dept., UC Irvine (1992).
• Data compression. 1993 McGraw-Hill Yearbook of Science and Technology, McGraw-Hill, New York (1992) 91-93.
• Parallel data compression. (with L.M. Stauffer) Tech. Rpt. 91-44 revised, ICS Dept., UC Irvine (1993).
• Parsing algorithms for dictionary compression on the PRAM. (with L.M. Stauffer) Proc. IEEE Data Compression Conference, Snowbird UT, IEEE (1994) 136-145.
• PRAM algorithms for static dictionary compression. (with L.M. Stauffer) Proc. International Parallel Processing Symposium, Cancun Mexico, IEEE (1994) 344-348.
• Systolic self-organizing lists under transpose. (with L.M. Stauffer) IEEE Trans. on Parallel and Distributed Systems 6,1 (1995) 102-105.
• Dictionary compression on the PRAM. (with L.M. Stauffer) Parallel Processing Letters 7,3 (1997) 297-308.
• Data compression. McGraw-Hill Encyclopedia of Science and Technology (8th ed.) vol. 5, McGraw-Hill, New York, 1997, pp. 31-33.

• An insertion technique for one-sided height-balanced trees. Comm. ACM 19,8 (1976) 471-473.
• Faster construction of optimal binary split trees. (with J.H. Hester, S.-H.S. Huang, and C.K. Wong) Jour. Algorithms 7,3 (1986) 412-424.
• Generation of optimal binary split trees. (with J.H. Hester) Proc. 24th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1986) 308-313.
• Subtree weight ratios for optimal binary search trees. (with L.L. Larmore and M. Molodowitch) Tech. Rpt. 86-02, ICS Dept., UC Irvine (1986).
• Construction of optimal binary split trees in the presence of bounded access probabilities. (with J.H. Hester and L.L. Larmore) Journal of Algorithms 9,2 (1988) 245-253.
• A bounded-space tree traversal algorithm. (with S. Seiden) Information Processing Letters 47 (1993) 215-219.
• The time complexity of decision tree induction. (with J.K. Martin) Tech. Rpt. 95-27, ICS Dept., UC Irvine (1995).
• On the complexity of learning decision trees. (with J.K. Martin) Proc. 4th Int. Symp. on Artif. Intell. and Math., Fort Lauderdale, FL (1996).

• A lower worst-case complexity for searching a dictionary. Proc. 16th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1978) 50-53.
• On the complexity of searching a set of vectors. SIAM Journal on Computing 9,1 (1980) 126-129.
• Self-organizing linear search. (with J. Hester) Computing Surveys 17,3 (1985) 295-311.
• Self-organizing search lists using probabilistic backpointers. (with J. Hester) Comm. ACM 30,12 (1987) 1074-1079.
• Improved combinatorial group testing for real-world problem sizes, (with D. Eppstein and M.T. Goodrich) Workshop on Algorithms and Data Structures (WADS) (2005), in Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, Berlin, 2005, 86-98.
  Expanded version: Improved combinatorial group testing algorithms for real-world problem sizes, SIAM J. on Computing to appear.
• Efficient parallel algorithms for dead sensor diagnosis and multiple access channels, (with M.T. Goodrich) Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA '06), Cambridge MA (2006) 118-127. Preliminary version, Improved adaptive group testing algorithms, presented at DIMACS Workshop on Combinatorial Group Testing, May 2006.

• Parallel algorithms for the transitive closure and the connected component problems. Proc. 8th Annual Symp. on Theory of Computing, Hershey PA, ACM (1976) 55-57.
• Fast parallel sorting algorithms. Comm. ACM 21,8 (1978) 657-661.
• Computing connected components on parallel computers. (with A.K. Chandra and D.V. Sarwate) Comm. ACM 22,8 (1979) 461-464.
• Election processes in distributed systems. Proc. 18th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1980) p.823.
• Decentralized extrema-finding in circular configurations of processors. (with J.B. Sinclair) Comm. ACM 23,11 (1980) 627-628.
• An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes. (with M. Kumar) Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1981). IEEE Trans. on Computers C-32,3 (1983) 254-264.
• Parallel graph algorithms without memory conflicts. Proc. 20th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1982) 257-263.
• A parallel solution for the minimum spanning tree problem. (with D.J. Volper) Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1983) 680-684.

• Breaking a paragraph into lines in linear time. (with L.L. Larmore) Proc. 22nd Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1984) 478-487.
• Efficient optimal pagination of scrolls. (with L.L. Larmore) Comm. ACM 28,8 (1985) 854-856.
• The least weight subsequence problem. (with L.L. Larmore) Proc. 26th Annual Symp. on Foundations of Computer Science, Portland Oregon, IEEE (1985) 137-143. SIAM J. on Computing 16,4 (1987) 628-638.
• New applications of failure functions. (with L.L. Larmore) Journal ACM 34,3 (1987) 616-625.
• The traveler's problem. (with L.L. Larmore) Journal of Algorithms 13 (1992) 148-160.

• Permutations of the elements of a matrix by column and row rotations. (with E.C. Horvath) Comp. Sci. Lab. TR-111, Princeton University (1972).
• A class of dynamic memory allocation algorithms. Comm. ACM 16,10 (1973) 615-618.
• A slightly better bound for the vertex connectivity problem. Proc. Conf. of Info. Sci. and Systems, Baltimore MD, Johns Hopkins Univ. (1975) 257-258.
• A polynomial-time algorithm for the knapsack problem with two variables. (with C.K. Wong) Journal ACM 23,1 (1976) 147-154.
• Approximate algorithms for some generalized knapsack problems. (with A.K. Chandra and C.K. Wong) Theoretical Computer Science 3,3 (1976) 293-304.
• Bin packing with geometric constraints in computer network design. (with A.K. Chandra and C.K. Wong) Operations Research 26,5 (1978) 760-772.
• Upper and lower bounds for graph-diameter problems. (with C.K. Wong) Journal of Comb. Theory (B) 26,1 (1979) 66-74.
• Average case analysis of marking algorithms. (with L.L. Larmore) Proc. 22nd Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1984) 508-509. SIAM Journal on Computing 15,4 (1986) 1069-1074.
• Tools for efficient analysis of concurrent software systems. (with R.R. Razouk) Proc. of SOFTFAIR II, A Second Conference on Software Development Tools, Techniques, and Alternatives, San Francisco CA (1985).
• Improved update/query algorithms for the interval valuation problem. (with D.J. Volper) Information Processing Letters 24 (1987) 307-310.
• Lower bounds for the stable marriage problem and its variants. (with C. Ng) SIAM J. on Computing 19,1 (1990) 71-77.
• Three-dimensional stable matching problems. (with C. Ng) SIAM J. Discr. Math. 4,2 (1991) 245-252.
• Shortest paths in orthogonal graphs. (with S. Bhatia and I.D. Scherson) Proc. 29th Annual Allerton Conf. on Comm., Control, and Computing, Monticello IL, Univ. of Ill. (1991) 488-497.
• Average case analysis of learning k-CNF concepts. (with M.J. Pazzani) Proc. Ninth International Machine Learning Conference, Aberdeen Scotland, Morgan Kaufmann, San Mateo (1992) 206-211.
• Average case analysis of k-CNF and k-DNF learning algorithms. (with M.J. Pazzani and K. Ali) Computational Learning Theory and Natural Learning Systems: Constraints and Prospects, S. Hanson, M. Kearns, T. Petsche and R. Rivest, ed., MIT Press, Cambridge, Mass., 1994, 15-28.
• Finding succinct minimal perfect hashing functions. (with S. Seiden) Information Processing Letters 51 (1994) 283-288.
• Choosing subsets with maximum weighted average. (with D. Eppstein) Tech. Rpt. 95-12, ICS Dept., UC Irvine (1995). Proc. 5th MSI Workshop on Computational Geometry, Stonybrook NY (1995) 7-8. Journal of Algorithms 24 (1997) 177-193.
• Small sample statistics for classification error rates, I: Error rate measurements. (with J.K. Martin) Tech. Rpt. 96-21, ICS Dept., UC Irvine (1996).
• Small sample statistics for classification error rates, II: Confidence intervals and significance tests. (with J.K. Martin) Tech. Rpt. 96-22, ICS Dept., UC Irvine (1996).
• Bounds on the number of string subsequences, Proc. Symp. on Combinatorial Pattern Matching. Warwick UK, Lecture Notes in Computer Science, Springer-Verlag, Berlin (1999) 115-122.
• Geometric thickness of complete graphs. (with M. Dillencourt and D. Eppstein) J. Graph Algorithms and Applications 4,3 (2000) 5-17. Preliminary version in Graph Drawing: 6th Int'l Symp. (GD '98), Montreal Canada, Lecture Notes in Computer Science, vol. 1547, Springer-Verlag, Berlin (1998) 102-110. Reprinted in Graph Algorithms and Applications 2, Giuseppe Liotta, Robert Tamassia, and Ioannis G Tollis, ed., (2004).
• Tight bounds on the number of string subsequences. (with M. Regnier) Journal of Discrete Algorithms 1,1 (2000) 123-132.
• Low power address encoding using self-organizing lists. (with M. Mamidipaka and N. Dutt) Proc. ACM/IEEE Int'l Symp. on Low Power Electronics and Design, Huntington Beach CA (2001) 188-193.
• Efficient power reduction techniques for time multiplexed address buses. (with M. Mamidipaka and N. Dutt) Proc. 15th ACM Int'l Symp. on System Synthesis, Kyoto (2002) 207-212.
• Adaptive low power address encoding techniques using self-organizing lists. (with M. Mamidipaka and N. Dutt) IEEE Trans. on Very Large Scale Integration Systems 11,5 (2003) 827-834.