IEICE Technical Report

Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380

Theoretical Foundations of Computing

Workshop Date : 2013-03-18 / Issue Date : 2013-03-11

COMP2012-52
On the eternal vertex cover number of trees composed of elementary bipartite graphs
Shota Inoue, Hisashi Araki, Toshihiro Fujito (Toyohashi Univ. of Tech)
pp. 1 - 4

COMP2012-53
Reservoir sampling in stream using O(log log n) space
Naoto Sonoda, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita (Kyushu Univ.)
pp. 5 - 12

COMP2012-54
[Tutorial Lecture] Introduction to Computational Complexity Theory (2):Algorithmic Approaches to Lower Bounds of Computational Complexity
Akinori Kawachi (Tokyo Inst. of Tech.)
p. 13

COMP2012-55
Auxiliary Skip Links for Quick Traversal of ZDDs to Manipulate Large-Scale Sparse Matrices
Shin-ichi Minato (Hokkaido Univ.)
pp. 15 - 22

COMP2012-56
Compact and Fast Indices Based on Zero-Suppressed Binary Decision Diagrams
Shuhei Denzumi (Hokkaido Univ.), Jun Kawahara (NAIST), Koji Tsuda (AIST/JST), Hiroki Arimura (Hokkaido Univ.), Shin-ichi Minato (Hokkaido Univ./JST), Kunihiko Sadakane (NII)
pp. 23 - 30

COMP2012-57
A note on lower bounds of the girth of planar C_7-colorable graphs
Tatsuo Asano, Akihiro Uejima (Osaka Electro-Comm. Univ.)
pp. 31 - 38

COMP2012-58
Comparative evaluation of two constructions of Hamiltonian circuits for generating picturesque mazes with illusory images
Fuhito Yanagitani, Akihiro Uejima (Osaka Electro-Comm. Univ.)
pp. 39 - 46

COMP2012-59
A New Exact Algorithm for the Maximum Weight Clique Problem Based on an Upper Bound Calculated by Dynamic Programming
Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, Sumio Masuda (Kobe Univ.)
pp. 47 - 53

COMP2012-60
Schnorr and Kurtz randomness versions of Merkel's criterion
Kenshi Miyabe (Kyoto Univ.)
pp. 55 - 59

COMP2012-61
An extension of code by introducing partial orders on codewords
Etsuro Moriya (Waseda Univ.)
pp. 61 - 68

COMP2012-62
[Fellow Memorial Lecture] The significance and power of computation theory: The role in information society
Takeshi Tokuyama (Tohoku Univ.)
p. 69

Note: Each article is a technical report without peer review, and its polished version will be published elsewhere.

The Institute of Electronics, Information and Communication Engineers (IEICE), Japan