Skip to main content
SpringerLink
Log in
Book cover

Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics

International Conference IFIP TCS 2000 Sendai, Japan, August 17-19, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Jan Leeuwen

    1. Department of Computer Science Centrumgebouw Noord, Office A309, University of Utrecht, Utrecht, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Osamu Watanabe

    1. Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Masami Hagiya

    1. Graduate School of Science Department of Information Science, The University of Tokyo, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Peter D. Mosses

    1. Department of Computer Science, University of Aarhus, Aarhus C, Denmark

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Takayasu Ito

    1. Graduate School of Information Sciences Department of Computer and Mathematical Sciences, Tohoku University, Sendai, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1872)

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.99
Price excludes VAT (USA)
  • Compact, lightweight 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 (49 papers)

  1. Front Matter

    Pages I-XV
    Download chapter PDF

  2. Breaking and fixing the Needham-Schroeder public-key protocol using FDR

    1. Reconciling Two Views of Cryptography

      • Martí;n Abadi, Phillip Rogaway
      Pages 3-22

  3. Theory and Construction of Molecular Computers

    1. Theory and Construction of Molecular Computers

      • Masami Hagiya
      Pages 23-24

  4. On the hardness of the permanent

    1. List Decoding: Algorithms and Applications

      • Madhu Sudan
      Pages 25-41

  5. Approximation Algorithms for String Folding Problems

    1. Approximation Algorithms for String Folding Problems

      • Giancarlo Mauri, Giulio Pavesi
      Pages 45-58

  6. Fast multi-dimensional approximate string matching

    1. An Index for Two Dimensional String Matching Allowing Rotations

      • Kimmo Fredriksson, Gonzalo Navarro, Esko Ukkonen
      Pages 59-75

  7. Parallel Edge Coloring of a Tree on a Mesh Connected Computer

    1. Parallel Edge Coloring of a Tree on a Mesh Connected Computer

      • Chang -Sung Jeong, Sung-Up Cho, Sun-Chul Whang, Mi-Young Choi
      Pages 76-83

  8. Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs

    1. Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs

      • Ryuhei Uehara, Zhi -Zhong Chen
      Pages 84-98

  9. It Is on the Boundary: Complexity Considerations for Polynomial Ideals

    1. It Is on the Boundary: Complexity Considerations for Polynomial Ideals

      • Ernst W. Mayr
      Pages 99-99

  10. An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks

    1. An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks

      • Yoojin Chung, Kunsoo Park, Hyuk-Chul Kwon
      Pages 100-111

  11. Reducibility among combinatorial problems

    1. Task Distributions on Multiprocessor Systems

      • Evgeny V. Shchepin, Nodari N. Vakhania
      Pages 112-125

  12. Fast Interpolation Using Kohonen Self-Organizing Neural Networks

    1. Fast Interpolation Using Kohonen Self-Organizing Neural Networks

      • Olivier Sarzeaud, Yann Stéphan
      Pages 126-139

  13. Steganography Using Modern Arts

    1. Steganography Using Modern Arts

      • Carlo Blundo, Clemente Galdi
      Pages 140-151

  14. Gossiping in Vertex-Disjoint Paths Mode in d-dimensional Grids and Planar Graphs

    1. Trade-Offs between Density and Robustness in Random Interconnection Graphs

      • Philippe Flajolet, Kostas Hatzis, Sotiris Nikoletseas, Paul Spirakis
      Pages 152-168

  15. An effcient way for edge-connectivity augmentation

    1. The (σ + 1)-Edge-Connectivity Augmentation Problem without Creating Multiple Edges of a Graph

      • Satoshi Taoka, Toshimasa Watanabe
      Pages 169-185

  16. On the Approximability of NP-complete Optimization Problems

    1. On the Hardness of Approximating Some NP-Optimization Problems Related to Minimum Linear Ordering Problem

      • Sounaka Mishra, Kripasindhu Sikdar
      Pages 186-199

  17. How Many People Can Hide in a Terrain ?

    1. Maximum Clique and Minimum Clique Partition in Visibility Graphs

      • Stephan Eidenbenz, Christoph Stamm
      Pages 200-212

  18. Language recognition and the synchronization of cellular automata

    1. Real-Time Language Recognition by Alternating Cellular Automata

      • Thomas Buchholz, Andreas Klein, Martin Kutrib
      Pages 213-225

  19. Inducing an order on cellular automata by a grouping operation

    1. Damage Spreading and μ-Sensitivity on Cellular Automata

      • Bruno Martin
      Pages 226-241

  20. Financial Applications of Monte Carlo and Quasi-Monte Carlo Methods

    1. Discrepancy Theory and Its Application to Finance

      • Shu Tezuka
      Pages 243-256
Back to top

Keywords

About this book

In 1996 the International Federation for Information Processing (IFIP) establ- hed its rst Technical Committee on foundations of computer science, TC1. The aim of IFIP TC1 is to support the development of theoretical computer science as a fundamental science and to promote the exploration of fundamental c- cepts, models, theories, and formal systems in order to understand laws, limits, and possibilities of information processing. This volume constitutes the proceedings of the rst IFIP International C- ference on Theoretical Computer Science (IFIP TCS 2000) { Exploring New Frontiers of Theoretical Informatics { organized by IFIP TC1, held at Tohoku University, Sendai, Japan in August 2000. The IFIP TCS 2000 technical program consists of invited talks, contributed talks, and a panel discussion. In conjunction with this program there are two special open lectures by Professors Jan van Leeuwen and Peter D. Mosses. The decision to hold this conference was made by IFIP TC1 in August 1998, and since then IFIP TCS 2000 has bene ted from the e orts of many people; in particular, the TC1 members and the members of the Steering Committee, the Program Committee, and the Organizing Committee of the conference. Our special thanks go to the Program Committee Co-chairs: Track (1): Jan van Leeuwen (U. Utrecht), Osamu Watanabe (Tokyo Inst. Tech.) Track (2): Masami Hagiya (U. Tokyo), Peter D. Mosses (U. Aarhus).

Editors and Affiliations

  • Department of Computer Science Centrumgebouw Noord, Office A309, University of Utrecht, Utrecht, The Netherlands

    Jan Leeuwen

  • Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan

    Osamu Watanabe

  • Graduate School of Science Department of Information Science, The University of Tokyo, Tokyo, Japan

    Masami Hagiya

  • Department of Computer Science, University of Aarhus, Aarhus C, Denmark

    Peter D. Mosses

  • Graduate School of Information Sciences Department of Computer and Mathematical Sciences, Tohoku University, Sendai, Japan

    Takayasu Ito

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation