Skip to main content
  • Book
  • © 2009

Fundamental Problems in Computing

Essays in Honor of Professor Daniel J. Rosenkrantz

  • A convenient collection of many seminal papers in computer science authored by Professor Daniel J. Rosenkrantz
  • Contains contributed chapters authored by well known researchers
  • Chapters cover a variety of important topics in computer science (e.g. algorithm analysis, complexity of voting systems, computational epidemiology, concurrency control for databases)
  • Chapters are suitable for self-study by graduate students in computer science and applied mathematics
  • Includes supplementary material: sn.pub/extras

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.00
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (18 chapters)

  1. Front Matter

    Pages i-xxi
  2. Selected Reprints from Professor Rosenkrantz’s Seminal Contributions

    1. Front Matter

      Pages 1-1
    2. Attributed Translations

      • P. M. Lewis, D. J. Rosenkrantz, R. E. Stearns
      Pages 13-43
    3. An analysis of several heuristics for the traveling salesman problem

      • Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis II
      Pages 45-69
    4. System Level Concurrency Control for Distributed Database Systems

      • Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis II
      Pages 71-98
    5. Consistency and serializability in concurrent database systems

      • D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis II
      Pages 99-132
    6. The Complexity of Processing Hierarchical Specifications

      • Daniel J. Rosenkrantz, Harry B. Hunt III
      Pages 209-240
    7. Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

      • R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III
      Pages 241-266
    8. Efficient Algorithms for Segmentation of Item-Set Time Series

      • Parvathi Chundi, Daniel J. Rosenkrantz
      Pages 267-297
  3. Contributed Articles

    1. Front Matter

      Pages 299-299
    2. Sums-of-Products and Subproblem Independence

      • Richard E. Stearns, Harry B. Hunt III
      Pages 301-325
    3. An Optimistic Concurrency Control Protocol for Replicated Databases

      • Yuri Breitbart, Henry F. Korth, Avi Silberschatz
      Pages 327-351
    4. A Richer Understanding of the Complexity of Election Systems

      • Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe
      Pages 375-406
    5. Fully Dynamic Bin Packing

      • Zoran Ivković, Errol L. Lloyd
      Pages 407-434
    6. Online Job Admission

      • Sven O. Krumke, Rob van Stee, Stephan Westphal
      Pages 435-454

About this book

Fundamental Problems in Computing is in honor of Professor Daniel J. Rosenkrantz, a distinguished researcher in Computer Science. Professor Rosenkrantz has made seminal contributions to many subareas of Computer Science including formal languages and compilers, automata theory, algorithms, database systems, very large scale integrated systems, fault-tolerant computing and discrete dynamical systems. For many years, Professor Rosenkrantz served as the Editor-in-Chief of the Journal of the Association for Computing Machinery (JACM), a very prestigious archival journal in Computer Science. His contributions to Computer Science have earned him many awards including the Fellowship from ACM and the ACM SIGMOD Contributions Award.

Editors and Affiliations

  • Department of Computer Science, University at Albany—SUNY, Albany, USA

    S. S. Ravi

  • Bradley Dept. Electrical and Computer Engineering, Virginia Tech, Blacksburg, USA

    Sandeep K. Shukla

Bibliographic Information

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.00
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access