Current trends in theoretical computer science : the challenge of the new century / editors, G. Paun, G. Rozenberg, A. Salomaa.

Format:

Book

Contributor:

Păun, Gheorghe, 1950-

Rozenberg, Grzegorz.

Salomaa, Arto.

Language:

English

Subjects (All):

Computer science.

Electronic data processing--Distributed processing.

Electronic data processing.

Physical Description:

1 online resource (1319 p.)

Place of Publication:

[River Edge], NJ : World Scientific, c2004.

Language Note:

English

Summary:

This book is based on columns and tutorials published in the <i>Bulletin of the European Association for Theoretical Computer Science (EATCS)</i> during the period 2000-2003. It presents many of the most active current research lines in theoretical computer science. The material appears in two volumes, "Algorithms and Complexity" and "Formal Models and Semantics", reflecting the traditional division of the field. The list of contributors includes many of the well-known researchers in theoretical computer science. Most of the articles are reader-friendly and do not presuppose much knowledge o

Contents:

Volume 1 ; CONTENTS ; Preface ; CHAPTER1 ALGORITHMICS ; Introductory Remarks ; H-Coloring of Graphs ; Open Problems in the Theory of Scheduling ; Analysis of Algorithms (AOFA). Part I: 1993 - 1998 (""Dagstuhl Period"")

Analysis of Algorithms (AOFA). Part II: 1998 - 2000 (""Princeton-Barcelona-Gdansk"") Algorithm Engineering ; PRIMES E P (Without Assumptions) ; Selfish Task Allocation ; CHAPTER2 COMPUTATIONAL COMPLEXITY ; Introductory Remarks

A Physics-Free Introduction to the Quantum Computation Model The Division Breakthroughs ; Derandomization: A Brief Overview ; Recent Developments in Explicit Constructions of Extractors ; The Art of Uninformed Decisions: A Primer to Property Testing

Time-Space Lower Bounds for NP-Complete Problems CHAPTER3 DISTRIBUTED COMPUTING ; Introductory Remarks ; A Combinatorial Characterization of Properties Preserved by Antitokens ; Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation

Distributed Communication Algorithms for Ad-hoc Mobile Networks Selfish Routing in Non-Cooperative Networks: A Survey ; Distributed Algorithmic Mechanism Design: Recent Results and Future Directions ; Stability in Routing: Networks and Protocols ; CHAPTER4 NATURAL COMPUTING

Introductory Remarks

Notes:

Description based upon print version of record.

Includes bibliographical references and index.

ISBN:

9789812562494

9812562494

OCLC:

879025066