| Committee |
Date Time |
Place |
Paper Title / Authors |
Abstract |
Paper # |
| COMP |
2005-10-18
09:00 |
Miyagi |
Tohoku Univ. |
Queue layout of bipartite graph subdivisions
Miki Miyauchi (NTT) |
This paper studies the problem of queue layout of bipartite graph subdivisions. A k-queue layout of a graph consists of ... [more] |
COMP2005-36
pp.1-5 |
| COMP |
2005-10-18
09:35 |
Miyagi |
Tohoku Univ. |
Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends
Xiao Zhou, Takao Nishizeki (Touhoku Univ.) |
[more] |
COMP2005-37
pp.7-14 |
| COMP |
2005-10-18
10:25 |
Miyagi |
Tohoku Univ. |
An asynchronous cellular space in which synchronous reversible cellular automata can be embedded
Jin-Shan Qi, Kenichi Morita (Hiroshima Univ.) |
We proposed a 2-dimensional 2-state asynchronous cellular automaton in which asynchronous logic elements called a rotary... [more] |
COMP2005-38
pp.15-20 |
| COMP |
2005-10-18
11:00 |
Miyagi |
Tohoku Univ. |
Margin Preserving Projection with Limited Randomness and Embedding to Boolean Space
Tatsuya Watanabe, Eiji Takimoto, Kazuyuki Amano, Akira Maruoka (Tohoku Univ.) |
Learning large margin classifiers is one of the most important problems in machine learning.
However, it is hard to fin... [more] |
COMP2005-39
pp.21-28 |
| COMP |
2005-10-18
13:15 |
Miyagi |
Tohoku Univ. |
[Tutorial Lecture]
An approach for obtaining the lower bounds on circuit complexity with mathematical programming
Kazuyuki Amano (Tohoku Univ.) |
[more] |
|
| COMP |
2005-10-18
14:30 |
Miyagi |
Tohoku Univ. |
Hamiltonian laceability of bubble-sort graphs with edge faults
Toru Araki (Iwate Univ.), Yosuke Kikuchi (JST) |
It is known that the $n$-dimensional bubble-sort graph $B_n$ is bipartite, $(n-1)$-regular, and has $n!$ vertices.
We f... [more] |
COMP2005-40
pp.29-35 |
| COMP |
2005-10-18
15:05 |
Miyagi |
Tohoku Univ. |
Compressing Compressed Data Structures
Kunihiko Sadakane (Kyushu Univ.), Roberto Grossi (Pisa Univ.) |
Succinct data structures are the ones which are compressed into nearly
the information-theoretic lower bound while supp... [more] |
COMP2005-41
pp.37-44 |
| COMP |
2005-10-18
15:55 |
Miyagi |
Tohoku Univ. |
Convex Drawings of Plane Graphs of Minimum Outer Apices
Kazuyuki Miura (Fukushima Univ.), Machiko Azuma, Takao Nishizeki (Tohoku Univ.) |
In a convex drawing of a plane graph $G$,
every facial cycle of $G$ is drawn as a convex polygon.
A polygon for the ou... [more] |
COMP2005-42
pp.45-51 |
| COMP |
2005-10-18
16:30 |
Miyagi |
Tohoku Univ. |
On the Graph Orientation of Minimizing the Maximum Outdegree
Yuichi Asahiro (Kyushu Sangyo Univ.), Eiji Miyano (Kyushu Inst. of Tech.), Hirotaka Ono (Kyushu Univ.), Kouhei Zenmyo (Kyushu Inst. of Tech.) |
[more] |
COMP2005-43
pp.53-60 |
| COMP |
2005-10-19
09:00 |
Miyagi |
Tohoku Univ. |
A quantum protocol to win the graph colouring game on all Hadamard graphs
David Avis (McGill Univ.), Jun Hasegawa (Univ. of Tokyo/JST), Yosuke Kikuchi (JST), Yuuya Sasaki (Univ. of Tokyo) |
This paper deals with graph colouring games, an example of pseudo-telepathy,
in which
two provers can convince a verif... [more] |
COMP2005-44
pp.1-6 |
| COMP |
2005-10-19
09:35 |
Miyagi |
Tohoku Univ. |
Automated Competitive Analysis of Online Problems
Takashi Horiyama, Kazuo Iwama, Jun Kawahara (Kyoto Univ.) |
In this paper we study the 2-Bin Exchangeable Online Knapsack Problem (2EOK)
which is an extension of the 2-Bin Removab... [more] |
COMP2005-45
pp.7-12 |
| COMP |
2005-10-19
10:10 |
Miyagi |
Tohoku Univ. |
An Approximate Algorithum for Pricing European-Asian Options
Takehisa Sekino, Akiyoshi Shioura, Takeshi Tokuyama (Tohoku Univ.) |
[more] |
COMP2005-46
pp.13-18 |
| COMP |
2005-10-19
11:00 |
Miyagi |
Tohoku Univ. |
Monotone DNFs that Minimize/Maximize the Number of Satisfying Assignments
Kazuyuki Amano (Tohoku Univ.), Takayuki Sato (Sendai Nat. Col. Tech.), Akira Maruoka (Tohoku Univ.) |
[more] |
COMP2005-47
pp.19-24 |
| COMP |
2005-10-19
11:35 |
Miyagi |
Tohoku Univ. |
Some sufficient conditions to solve the learning problem of simple deterministic languages from queries and counterexamples
Yasuhiro Tajima, Yoshiyuki Kotani (Tokyo Univ. of Agri and Tech.), Etsuji Tomita (Univ. of Electro-Comm.) |
It is unknown that polynomial time learnability of simple deterministic languages from membership
queries and counterex... [more] |
COMP2005-48
pp.25-30 |