IEICE Technical Report

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

Theoretical Foundations of Computing

Workshop Date : 2007-10-16 / Issue Date : 2007-10-09

COMP2007-41
NP-Completeness of the Stable Roommates Problem with Triple Rooms
Kazuya Okamoto, Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.)
pp. 1 - 6

COMP2007-42
Complexity of Finding Most Likely Solutions
Osamu Watanabe (Tokyo Inst. of Tech.)
pp. 7 - 12

COMP2007-43
An exact algorithm for #25SAT based on dynamic proframming on path decomposition
Mitsuo Motoki (JAIST)
pp. 13 - 17

COMP2007-44
Connectedness of domino tilings with impurities
Hirotaka Ono (Kyushu Univ.), Taizo Sadahiro (Pref. Univ. of Kumamoto)
pp. 19 - 24

COMP2007-45
A winning strategy for Snaky with one handicap
Hiro Ito, Hiromitsu Miyagawa (Kyoto Univ.)
pp. 25 - 32

COMP2007-46
An O(2^0.24945n)-time and Polynomial-space Algorithm
Hiroaki Nakanishi, Etsuji Tomita (Univ. of Electro-Comun.)
pp. 33 - 40

COMP2007-47
A polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers
Kazushi Seino (UEC/TSOL), Etsuji Tomita, Mitsuo Wakatsuki (UEC)
pp. 41 - 48

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