Invited Talks

We plan several invited talks in wide ranges of theory and practice.

Chair: Ferdinand Peper

Speaker: Kenichi Morita (Hiroshima University, Japan)

Title: Reversible Computing Systems, Logic Circuits, and Cellular Automata

Reversible computing is a paradigm of computation that reflects physical reversibility, and will become important when we develop future computing systems that directly utilize microscopic physical phenomena for logical operations. In this survey we discuss, from a theoretical point of view, how a reversible computer is implemented as a reversible logic circuit, how a reversible logic circuit is composed of reversible logic elements, and how a reversible logic element can be realized in a physically reversible system. We shall see that, in spite of the constraint of reversibility, universal reversible computers can be constructed by very simple reversible primitives, and that in these systems computation is often carried out in a very unique and different manner from conventional computing systems.

Chair: Tsutomu Yoshinaga

Speaker: Mitsuo Yokokawa (Riken, Japan)

Title: The K Computer and Its Application

The K computer is a distributed memory supercomputer system with 82,944 compute nodes and 5,184 I/O nodes that was jointly developed by RIKEN and Fujitsu as a Japanese national project. Its development began in 2006 and was completed in June, 2012. By achieving the LINPACK performance of 10.51 peta-FLOPS, the K computer ranked first for two consecutive TOP500 list in June and November 2011. During its adjustment, part of the K computer was served, gradually increasing computing resources, to experts in computational science as a trial and was used for performance optimization of users’ application codes.

Chair: Qi-Wei Ge

Speaker: Toshimasa Watanabe (Hiroshima University, Japan)

Title: Computational Complexity Analysis and Algorithm Design for Combinatorial Optimization Problems

This paper shows summary of the author’s research subjects from 1973 through 2012. The subjects are as follows.

• A: Finite Automata and Semigroups
• B: Time Complexity Analysis and NP-Hardness
• C: Connectivity Augmentation and Related Problems
• D: Petri Nets
• E: Graph and/or Combinatorial Theoretical Approach to Printed Wiring Board Design
• F: Parallel and/or Branch-and-Bound Algorithms
• G: Computing Experiment-based Evaluation of Algorithms
• H: System Design and Implementation
• I: Special Educational Activities

Chair: Hideharu Amano

Speaker: Hong Shen (University of Adelaide, Australia)

Title: Approximate Algorithms for Survivable Network Design

Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. An interesting subject that has attracted great effort is how to design network topologies with a minimum network resource usage in terms of cost that provides a relibility guarantee. As problems on this subject, like most other network optimization problems, are well-known NP-hard even in their simplest form, design of effective solutions with a guaranteed approximation ratio from the optimal solution has been a major research focus of great significance for both theory and applications. This survery summarizes major existing techniques and results for solving some central problems in designing survivable networks including the minimal connected subgraph problem, the survivable network design problem and the Steiner minimal network problem.