| IEICE Technical Committee Submission System Conference Schedule |
Online Proceedings [Sign in] Tech. Rep. Archives |
Technical Committee on Theoretical Foundations of Computing (COMP) (Searched in: 2008)
Search Results: Keywords 'from:2008-10-10 to:2008-10-10'
| Committee | Date Time | Place | Paper Title / Authors | Abstract | Paper # | |
| COMP | 2008-10-10 09:00 |
Miyagi | Tohoku Univ. | Bit-Parallel Tree Pattern Matching Algorithms for Trees with Restricted Labels Hiroaki Yamamoto (Shinshu Univ.), Daichi Takenouchi (NTT-AT)  COMP2008-34 |
[more] | COMP2008-34 pp.1-8 |
| COMP | 2008-10-10 09:30 |
Miyagi | Tohoku Univ. | Packing Alignment and Its Application to Music Mining Atsuyoshi Nakamura, Mineichi Kudo (Hokkaido Univ.) COMP2008-35 |
We propose packing alignment as an alignment for sequences of lengthened symbols like musical notes. Furthermore, we co... [more] |
COMP2008-35 pp.9-16 |
| COMP | 2008-10-10 10:00 |
Miyagi | Tohoku Univ. | On the Complexity of Reconfiguration Problems Takehiro Ito (Tohoku Univ.), Erik D. Demaine, Nicholas J. A. Harvey (MIT), Christos H. Papadimitriou (UC Berkeley), Martha Sideri (AUEB), Ryuhei Uehara (JAIST), Yushi Uno (Osaka Prefecture Univ.) COMP2008-36 |
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a pr... [more] | COMP2008-36 pp.17-24 |
| COMP | 2008-10-10 10:45 |
Miyagi | Tohoku Univ. | A Class of Smallest Four-State Firing Squad Synchronization Protocols for One-Dimensional Ring Cellular Automata Hiroshi Umeo, Naoki Kamikawa (Univ. of Osaka Electro-Comm.), Jean Baptiste Yun\`es (LIAFA-Univ.) COMP2008-37 |
An existence or non-existence of five-state firing squad synchronization protocol has been a longstanding and famous ope... [more] | COMP2008-37 pp.25-31 |
| COMP | 2008-10-10 11:15 |
Miyagi | Tohoku Univ. | A Simple Succinct Representation of Balanced Parentheses Sequences Kunihiko Sadakane (Kyushu U) COMP2008-38 |
The balanced parentheses sequence (BP) is a representation of ordinal trees which was extensively studied recently. An... [more] |
COMP2008-38 pp.33-40 |
| COMP | 2008-10-10 13:30 |
Miyagi | Tohoku Univ. | Computing the Tutte Polynomial of a Graph via BDD Revisited Hiroshi Imai (Univ. Tokyo), Keiko Imai (Chuo Univ.), Yoshitake Matsumoto, Sonoko Moriyama (Univ. Tokyo) COMP2008-39 |
The computation of the Tutte polynomial of a graph, even a planar one, is \#P-complete, and yet more efficient exponent... [more] |
COMP2008-39 pp.41-46 |
| COMP | 2008-10-10 14:00 |
Miyagi | Tohoku Univ. | Lower bounds on quantum query complexity for decision trees Hideaki Fukuhara (Tohoku Univ.), Eiji Takimoto (Kyushu Univ.) COMP2008-40 |
[more] | COMP2008-40 pp.47-54 |
| COMP | 2008-10-10 14:30 |
Miyagi | Tohoku Univ. | Partitioning a Weighted Tree to Subtrees of Almost Uniform Size Takehiro Ito (Tohoku Univ.), Takeaki Uno (NII), Xiao Zhou, Takao Nishizeki (Tohoku Univ.) COMP2008-41 |
Assume that each vertex of a graph $G$ is assigned a nonnegative integer weight and that $l$ and $u$ are integers such t... [more] | COMP2008-41 pp.55-61 |
| COMP | 2008-10-10 15:15 |
Miyagi | Tohoku Univ. | Size-Energy Tradeoff for Threshold Logic Circuits Computing MOD Functions Kei Uchizawa (Tohoku Univ.), Eiji Takimoto (Kyushu Univ.), Takao Nishizeki (Tohoku Univ.) COMP2008-42 |
A threshold logic circuit $C$ computing a Boolean function MOD$_m: \{ 0，1\}^n \to \{0, 1\}$ outputs ``0'' if the number ... [more] | COMP2008-42 pp.63-69 |
| COMP | 2008-10-10 15:45 |
Miyagi | Tohoku Univ. | The carving-width of even grids Masanobu Furuse, Kyohei Kozawa, Yota Otachi, Koichi Yamazaki (Gunma Univ.) COMP2008-43 |
In [Call routing and the ratcatcher. Combinatorica 14(2) (1994) 217--241], Seymour and Thomas introduced the concept of... [more] |
COMP2008-43 pp.71-75 |
| COMP | 2008-10-10 16:15 |
Miyagi | Tohoku Univ. | Divide-and-Conquer Approach for Preemptive Scheduling Problems with Controllable Processing Times Natalia Shakhlevich (Univ. Leeds), Akiyoshi Shioura (Tohoku Univ.), Vitaly Strusevich (Univ. Greenwich) COMP2008-45 |
[more] | COMP2008-45 pp.85-92 |
[Return to Top Page]