| Committee |
Date Time |
Place |
Paper Title / Authors |
Abstract |
Paper # |
| COMP |
2006-03-22
13:00 |
Tokyo |
The University of Electro-Communications |
A polynomial time algorithm for finding a minimum weighted maximal independent set in weighted chordal graph
Ryosuke Kondo (T.I.T) |
[more] |
COMP2005-57
pp.1-8 |
| COMP |
2006-03-22
13:35 |
Tokyo |
The University of Electro-Communications |
On an Efficient Clustering Algorithm for Dynamic Sensor Networks with Considering Mergence and Partition of Clusters
Shintaro Miyanaga, Yoshiaki Katayama, Koichi Wada, Naohisa Takahashi (NIT), Motonari Kobayashi, Masanori Morita (NTT DoCoMo,Inc.) |
The network formed only with a wireless nodes communicating via radio called wireless ad hoc network(WANET).
We propose... [more] |
COMP2005-58
pp.9-16 |
| COMP |
2006-03-22
14:30 |
Tokyo |
The University of Electro-Communications |
Approximability and Non-approximability of the Minimum Block Transfer Problem
Yuichi Asahiro (Kyushu Sangyo Univ.), Tetsuya Furukawa (Kyushu Univ.), Keiichi Ikegami, Eiji Miyano (Kyushu Inst. of Tech.) |
[more] |
COMP2005-59
pp.17-24 |
| COMP |
2006-03-22
15:05 |
Tokyo |
The University of Electro-Communications |
Experimental analyses of approximation algorithms for the maximum weighted independent set problem on d-claw free graphs
Yota Otachi, Koichi Yamazaki (Gunma Univ.) |
A $d$-claw is an induced subgraph isomorphic to $K_{1,d}$. A graph is $d$-claw free if it has no $d$-claws. Several appr... [more] |
COMP2005-60
pp.25-30 |
| COMP |
2006-03-22
16:00 |
Tokyo |
The University of Electro-Communications |
Canonical Tree Representation of Distance Hereditary Graphs with Applications
Ryuhei Uehara (JAIST), Takeaki Uno (NII) |
The class of distance hereditary graphs consists of
the isometric graphs.
That is, for each pair of vertices,
its d... [more] |
COMP2005-61
pp.31-36 |
| COMP |
2006-03-22
16:35 |
Tokyo |
The University of Electro-Communications |
HITS on Today's Web
Yu Tezuka, Yasuhito Asano, Takao Nishizeki (Tohoku Univ.) |
[more] |
COMP2005-62
pp.37-44 |
| COMP |
2006-03-23
09:00 |
Tokyo |
The University of Electro-Communications |
Increasing the Success Probability of PPSZ-type Satisfiability Testing
Kazuo Iwama, Suguru Tamaki (Kyoto Univ.) |
Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound
for 3SAT by modifying the PPSZ-type algorithm in
... [more] |
COMP2005-63
pp.1-6 |
| COMP |
2006-03-23
09:35 |
Tokyo |
The University of Electro-Communications |
Complexity of the pairing strategy for Shannon switching game
Ryosuke Takahashi, Eiji Takimoto, Akira Maruoka (Tohoku Univ.) |
Shannon switching game is a game where two players alternately place stones on the vertices of a given graph. The first ... [more] |
COMP2005-64
pp.7-14 |
| COMP |
2006-03-23
10:30 |
Tokyo |
The University of Electro-Communications |
Parsing using syntactic feature
Yuu Tsuruoka (UEC) |
[more] |
COMP2005-65
pp.15-21 |
| COMP |
2006-03-23
11:05 |
Tokyo |
The University of Electro-Communications |
Improved Lower Bounds for Families of ε -Approximate k-Restricted Min-Wise Independent Permutations
Toshiya Itoh, Tatsuya Nagatani (Tokyo Inst. of Tech.) |
A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool~of~indexing replicated documents o... [more] |
COMP2005-66
pp.23-30 |
| COMP |
2006-03-23
13:10 |
Tokyo |
The University of Electro-Communications |
[Fellow Memorial Lecture]
Invited Talk as a New Fellow
Kazuo Iwama (Kyoto Univ.) |
[more] |
|
| COMP |
2006-03-23
14:30 |
Tokyo |
The University of Electro-Communications |
Recognition of Tree-Shellable Boolean Functions with several Restrictions
Nao Katougi, Yasuhiko Takenaga, Takashi Ishibashi (UEC) |
A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number... [more] |
COMP2005-67
pp.31-37 |
| COMP |
2006-03-23
15:05 |
Tokyo |
The University of Electro-Communications |
Improvement of the Round Complexity of Perfectly Concealing Bit Commitment Schemes
Yoshiharu Seri, Takeshi Koshiba (Saitama Univ.) |
We improve the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general ... [more] |
COMP2005-68
pp.39-46 |