Skip to main content
SpringerLink
Log in
Book cover

Fundamental Problems in Computing

Essays in Honor of Professor Daniel J. Rosenkrantz

  • Book
  • © 2009

Overview

Editors:
  1. S. S. Ravi

    1. Department of Computer Science, University at Albany—SUNY, Albany, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Sandeep K. Shukla

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • 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

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (18 chapters)

  1. Front Matter

    Pages i-xxi
    Download chapter PDF

  2. Selected Reprints from Professor Rosenkrantz’s Seminal Contributions

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Matrix Equations and Normal Forms for Context-Free Grammars

      • Daniel J. Rosenkrantz
      Pages 3-11

    3. Attributed Translations

      • P. M. Lewis, D. J. Rosenkrantz, R. E. Stearns
      Pages 13-43

    4. An analysis of several heuristics for the traveling salesman problem

      • Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis II
      Pages 45-69

    5. System Level Concurrency Control for Distributed Database Systems

      • Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis II
      Pages 71-98

    6. Consistency and serializability in concurrent database systems

      • D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis II
      Pages 99-132

    7. An efficient method for representing and transmitting message patterns on multiprocessor interconnection networks

      • P. J. Bernhard, D. J. Rosenkrantz
      Pages 133-162

    8. Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications

      • Lin Yu, Daniel J. Rosenkrantz
      Pages 163-208

    9. The Complexity of Processing Hierarchical Specifications

      • Daniel J. Rosenkrantz, Harry B. Hunt III
      Pages 209-240

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

    11. 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
      Download chapter PDF

    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. SNAPSHOT Isolation: Why Do Some People Call it SERIALIZABLE?

      • Philip Lewis
      Pages 353-373

    5. A Richer Understanding of the Complexity of Election Systems

      • Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe
      Pages 375-406

    6. Fully Dynamic Bin Packing

      • Zoran Ivković, Errol L. Lloyd
      Pages 407-434

    7. Online Job Admission

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

    8. A Survey of Graph Algorithms Under Extended Streaming Models of Computation

      • Thomas C. O’Connell
      Pages 455-476
Back to top

Keywords

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

Publish with us

Policies and ethics

Back to top

Search

Navigation