| IEICE Technical Committee Submission System Conference Schedule |
Online Proceedings [Sign in] Tech. Rep. Archives |
Technical Committee on Theoretical Foundations of Computing (COMP) (Searched in: 2007)
Search Results: Keywords 'from:2007-06-29 to:2007-06-29'
| Committee | Date Time | Place | Paper Title / Authors | Abstract | Paper # | |
| COMP | 2007-06-29 09:00 |
Hokkaido | Hokkaido University | A Computaional Complexity for finding a Maximum Clique in a Graph with Maximum Degree 4 Hiroaki Nakanishi, Etsuji Tomita (UEC)  COMP2007-18 |
The maximum clique problem is an NP-hard problem, and is difficult to solve efficiently. The trivial upper bound of its... [more] |
COMP2007-18 pp.1-7 |
| COMP | 2007-06-29 09:25 |
Hokkaido | Hokkaido University | Linear Time Enumeration of Isolated Bicliques with Part Size Proportion Bounded by Constants Hiromitsu Miyagawa, Hiro Ito, Kazuo Iwama (Kyoto Univ.) COMP2007-19 |
Problems for finding a maximum bipartite clique and enumerating maximal bipartite cliques for graphs are difficult. Alth... [more] | COMP2007-19 pp.9-16 |
| COMP | 2007-06-29 09:50 |
Hokkaido | Hokkaido University | Testing k-Edge-Connectivity of Digraphs Yuichi Yoshida, Hiro Ito (Kyoto Univ.) COMP2007-20 |
In this paper, we show constant time algorithm for testing whether a given degree-bounded digraph is $k$-edge-connected ... [more] | COMP2007-20 pp.17-23 |
| COMP | 2007-06-29 10:30 |
Hokkaido | Hokkaido University | Towards closing a gap between worst-case and average-case NP hardness Akinori Kawachi, Osamu Watanabe (Tokyo Inst. of Tech.) COMP2007-21 |
It is significant in the computational complexity theory and the foundations of cryptography to construct problems har... [more] |
COMP2007-21 pp.25-32 |
| COMP | 2007-06-29 10:55 |
Hokkaido | Hokkaido University | Deductive Inference for the Interiors and Exteriors of Horn Theories Kazuhisa Makino (Univ. of Tokyo), Hirotaka Ono (Kyushu Univ.) COMP2007-22 |
[more] | COMP2007-22 pp.33-39 |
| COMP | 2007-06-29 11:20 |
Hokkaido | Hokkaido University | Weighted Random Popular Matchings Toshiya Itoh, Osamu Watanabe (Tokyo Inst. of Tech.) COMP2007-23 |
Let A be the set of n applicants and I be the set of m items. We assume that the set A is partitioned into A_{1},A_{2}... [more] | COMP2007-23 pp.41-48 |
| COMP | 2007-06-29 14:15 |
Hokkaido | Hokkaido University | Simple efficient algorithm for MPQ-tree of an interval graph Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara (JAIST) COMP2007-24 |
An MPQ-tree is an informative data structure for an interval graph. We propose a simple algorithm that constructs an MPQ... [more] | COMP2007-24 pp.49-54 |
| COMP | 2007-06-29 14:40 |
Hokkaido | Hokkaido University | On the complexity of planar n/k-coloring problems Masakazu Shoji, Akihiro Uejima (Osaka Electro-Communication Univ.) COMP2007-25 |
This paper considers the {\it $n/k$-coloring problem} ({\it Circular Coloring}), which is a subproblem of the $H$-color... [more] |
COMP2007-25 pp.55-62 |
| COMP | 2007-06-29 15:05 |
Hokkaido | Hokkaido University | A Tight Upper Bound on Online Buffer Management for Two-port Shared-Memory Switches Koji Kobayashi, Shuichi Miyazaki, Yasuo Okabe (Kyoto Univ.) COMP2007-26 |
The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Q... [more] |
COMP2007-26 pp.63-70 |
| COMP | 2007-06-29 15:30 |
Hokkaido | Hokkaido University | A Difference-Optimal Algorithm for Gathering Autonomous Mobile Robots with Dynamic Compasses Taisuke Izumi, Yoshiaki Katayama, Nobuhiro Inuzuka, Koichi Wada (Nagoya Inst.of Tech.) COMP2007-27 |
Let us consider $n$ autonomous mobile robots that can move in a two dimensional plane. The gathering problem is one ... [more] |
COMP2007-27 pp.71-78 |
| COMP | 2007-06-29 16:10 |
Hokkaido | Hokkaido University | The Firing Squad Synchronization Problems for Number Patterns on 7-Segment Display Kazuya Yamashita (Univ. Toyama), Eigo Takemasa (Univ. Toyama/Nihon Softech), Mitsuru Sakai, Sadaki Hirose (Univ. Toyama) COMP2007-28 |
The firing squad synchronization problem, one of famous problems on cellular automata, was proposed by Myhill in around ... [more] | COMP2007-28 pp.79-84 |
| COMP | 2007-06-29 16:35 |
Hokkaido | Hokkaido University | On an Efficient Implementation of a DFA-based Algorithm for the Exetended Regular Expression Membership and Search Problems Hiroaki Yamamoto (Shinshu Univ.), Takashi Miyazaki (Nagano NCT) COMP2007-29 |
This paper addresses the following extended regular expression (EREs for short, that is, regular expressions with inte... [more] |
COMP2007-29 pp.85-92 |
| COMP | 2007-06-29 17:00 |
Hokkaido | Hokkaido University | Linear-Time Recognition of Tree Structures by Deterministic Linear Pushdown Tree Automata Akio Fujiyoshi (Ibaraki Univ.) COMP2007-30 |
In this paper, we introduce a deterministic linear pushdown tree automaton (deterministic L-PDTA) and some variations. I... [more] | COMP2007-30 pp.93-99 |
| COMP | 2007-06-29 17:25 |
Hokkaido | Hokkaido University | Succinct Array Structure for Patricia Trie Susumu Yata, Kazuhiro Morita, Masao Fuketa, Jun-ichi Aoe (Tokushima Univ.) COMP2007-31 |
A patricia trie is available by removing internal nodes which have just onechild from a binary trie, and is applied to f... [more] | COMP2007-31 pp.101-106 |
[Return to Top Page]