Report on TGCOMP Meetings (Jan. - June, 2004)

This is a list of papers presented at TGCOMP meetings held January - June of 2004.

IMPORTANT NOTICE:
TGCOMP Meetings are norefereed meetings; that is, all proposed talks are accepted for the presentation. Although papers for the presented talks are published as TGCOMP Technical Reports, these are essentially equivalent to ordinary technical reports. Thus, there should be no problem of presenting these papers in refereed conferences and/or journals.

Less Important Notice:

k = key words, a = author(s), c = address, and e = e-mail address.

ALGORITHMS: ON GRAPHS

  1. On minimum k-edge-connectivity augmentation for specified vertices of a graph with degree constraints
    a: T. Mashima* and T. Watanabe
    k: augmentation problems, edge-splitting-off, linear time algorithms
    c: Dept. of Infor. Tech., Hiroshima International Univ., Hiroshima 737-0112
    e: mashima@it.hirokoku-u.ac.jp
  2. On the competitive analysis of stream merging algorithms for video-on-demand
    a: K. Maruchi and T. Itoh
    k: online scheduling, maximum bandwidth, total bandwidth
    c: Global Sci. Info. and Comp. Center, Tokyo Institute of Tech., Tokyo 152-8550
    e: titoh@dac.gsic.titech.ac.jp
  3. An exact algorithm for solving the maximum weighted clique problem with using comparability supergraphs
    a: K. Yamaguchi* , Y. Sakakibara and S. Masuda
    k: chromatic number, branch-and-bound algorithm
    c: Dept. of Electrical and Electronics Eng., Kobe Univ., Hyogo 657-8501
    e: ky@eedept.kobe-u.ac.jp
  4. Enumerating isolated subgraphs
    a: T. Osumi*, H. Ito and K. Iwama
    k: Web, clique, cut
    c: Dept. of Comm. and Comp. Eng., Grad. Sch. of Informatics, Kyoto University, Kyoto 606-8501
    e: osumi@lab2.kuis.kyoto-u.ac.jp
  5. Algorithms for point set matching with k-differences
    a: T. Akutsu*
    k: computational geometry, largest common point set, congruence
    c: Inst.. Chem. Res., Kyoto Univ., Kyoto 611-0011
    e: takutsu@kuicr.kyoto-u.ac.jp
  6. One edge addition to a complete binary tree maximizing total shortening path length
    a: K. Sawada*
    k: organization structure, graph theory
    c: Dept. of Inf. \& Mgt. Sci., Univ. of Mktg. \& Distr. Sci., Hyogo 651-2188
    e: sawada@umds.ac.jp
  7. Longest paths in small graph classes
    a: R. Uehara* and Y. Uno
    k: efficient algorithms, graph algorithms, graph classes, longest path problem
    c: Natural Science Faculty, Komazawa Univ., Tokyo 154-8525
    e: uehara@komazawa-u.ac.jp
  8. Drawing borders efficiently
    a: K. Iwama, K. Izumi, E. Miyano*, and H. Ono
    k: spreadsheet, border drawing problem, border style, NP-hardness, drawability
    c: Dept. of Systems Innovation and Informatics, Kyushu Inst. of Tech., Fukuoka 820-8502
    e: miyano@ces.kyutech.ac.jp

ALGORITHMS: ON STRINGS

  1. Approximate point pattern matching for musical sequences
    a: T. Suga* and S. Shimozono
    k: point pattern, approximate matching, musical score sequence
    c: Dept. of AI, Kyushu Inst. of Tech., Fukuoka 820-8502
    e: sin@ai.kyutech.ac.jp
  2. A space-efficient approximation algorithm for grammar-based compression
    a: H. Sakamoto*
    k: data compression, linear-time algorithm, context-free grammar
    c: Dept. of AI, Kyushu Inst. of Tech., Fukuoka 820-8502
    e: hiroshi@ai.kyutech.ac.jp
  3. Linear time off-line algorithm for text compression by longest-first substitution
    a: S. Inenaga, T. Funamoto, M. Takeda*, A. Shinohara
    k: data compression, CDAWG, suffix tree
    c: Dept. of Info., Kyushu University, Fukuoka 812-8581
    e: takeda@i.kyushu-u.ac.jp
  4. On the generative power of grammars for RNA secondary structure
    a: Y. Kato, H. Seki* and T. Kasami
    k: formal language theory, multiple context-free grammar, pseudoknot
    c: Grad. School of Info. Sci., Nara Inst. Sci. Tech., Nara 630-0192
    e: seki@is.aist-nara.ac.jp
  5. An efficient algorithm for computing mismatch tolerance of substrings
    a: T. Uno
    k: similar substring, micro array
    c: National Inst. of Informatics, Tokyo 101-8430
    e: uno@nii.jp
  6. VLDC pattern matching algorithms with allowing errors
    a: T. Kida*
    k: hamming distance, approximate string matching, bit-parallel
    c: Kyushu University Library, Kyushu Univ., Fukuoka, 812-8581
    e: kida@lib.kyushu-u.ac.jp
  7. Formulation of template discovery problem and an algorithm using substring amplification
    a: D. Ikeda*, Y. Yamada and S. Hirokawa
    k: common subsequence, information extraction, average case analysis, power-law distribution
    c: Computing and Communications Center, Kyushu Univ., Fukuoka 812-8581
    e: daisuke@cc.kyushu-u.ac.jp
  8. An improvement in compressed suffix array construction algorithms
    a: W. K. Hon, K. Sadakane* and W. K. Sung
    k: information retrieval
    c: Dept. of Comp. Sci. and Comm. Eng., Kyushu Univ., Fukuoka 812-8581
    e: sada@csce.kyushu-u.ac.jp

ALGORITHMS: ON SOME OTHER OBJECTS

  1. Approximating the stable marriage problem by local search
    a: K. Okamoto, S. Miyazaki* and K. Iwama
    k: stable matchings, incomplete lists, ties, approximation algorithms, approximation ratios
    c: Academic Center for Computing and Media Studies, Kyoto Univ., Kyoto 606-8501
    e: shuichi@kuis.kyoto-u.ac.jp
  2. Constant time generation of set partitions
    a: S. Kawano and S. Nakano*
    k: enumeration algorithm, Stirling number of the second kind, Bell number, gray code
    c: Dept. of Comp. Sci., Gunma Univ., Kiryu, Gunma, Japan 376-8515
    e: nakano@msc.cs.gunma-u.ac.jp
  3. Enumeration of Tsume-Shogi instances by the reverse method
    a: H. Nakatsuka, T. Horiyama*, and K. Iwama
    k: enumeration algorithm, Tsuji-Shogi, reverse method, knight problem
    c: Grad. School of Informatics, Kyoto Univ., Kyoto 606-8501
    e: horiyama@i.kyoto-u.ac.jp

COMBINATORICS / PROBABILISTIC ANALYSIS

  1. Double Horn extensions and restricted Horn extensions of a partially defined Boolean function
    a: M. Iida* and K. Makino
    k: extensions, Horn functions, knowledge base
    c: Dept. of Math. and Comp. Sci., Tokyo Institute of Tech., Tokyo 152-8552
    e: Masaomi.Iida@is.titech.ac.jp
  2. Explicit construction of k-wise nearly random permutations by iterated feistel transform
    a: T. Itoh*, T. Nagatani and J. Tarui
    k: Markov chain
    c: Global Sci. Info. and Comp. Center, Tokyo Institute of Tech., Tokyo 152-8550
    e: titoh@dac.gsic.titech.ac.jp
  3. Analysis for LRU caching with invalidation and timeout
    a: R. Hirade* and T. Hama
    k: poisson embedding, formal language, average-case analysis
    c: IBM Research, Tokyo Research Laboratory, Kanagawa 242-8502
    e: rhirade@jp.ibm.com
  4. A simple approximated annalysis of Markov process and its application to analysis of randomized algorithms
    a: J. Schneider and O. Watanabe*
    k: pseudo expectation, nonlinearity, average performance
    c: Dept. of Math. and Comp. Sci., Tokyo Inst. of Tech., Tokyo 152-8552
    e: watanabe@is.titech.ac.jp
  5. Non-LP orientations, non-line shellings and non-representable oriented matroids
    a: K. Fukuda, S. Moriyama*, and Y. Okamoto
    k: representability of oriented matroids
    c: Dept. of Comp. Sci., Univ. of Tokyo, Tokyo 113-0033
    e: moriso@is.s.u-tokyo.ac.jp
  6. Partitions with respect to functions and line digraphs
    a: H. Kawai and Y. Shibata*
    k: graph theory, line digraph, coloring
    c: Dept. of Comp. Sci., Gunma Univ., Kiryu, Gunma, Japan 376-8515
    e: shibata@msc.cs.gunma-u.ac.jp
  7. Embedding bipartite graphs into book space
    a: M. Miyauchi
    k: bipartite graph, book embedding, crossings of edges over the spine
    c: NTT Communication Science Lab., NTT Co., Kanagawa 243-0198
    e: miyauchi@theory.brl.ntt.co.jp

COMPUTATIONAL COMPLEXITY

    Subgraph connectivity problem
    a: E. Moriya and T. Nishida*
    k: computational complexity, NP-completeness, graph theory
    c: Sch. of educ., Dept. of Mathmatics, Waseda Univ., Tokyo 169-8050
    e: taitai@ruri.waseda.jp
  1. On computational complexity of the conjugacy problem for braids
    a: M. Matsuba and S. Tani*
    k: PSPACE, summit set
    c: Dept. of Comp. Sci. and Syst. Anal., Nihon Univ., Tokyo 156-8550
    e: sei-ichi@tani.cs.chs.nihon-u.ac.jp
  2. Improved lower bounds for competitive ratio of multi-queue switches in QoS networks
    a: T. Itoh* and T. Nagumo
    k: online algorithms, competitive analysis, quality of service, multi-priority model
    c: Global Sci. Info. and Comp. Center,Tokyo Institute of Tech., Tokyo 152-8550
    e: titoh@dac.gsic.titech.ac.jp
  3. Sublogarithmically space-bounded one-pebble alternating Turing machines with only universal states
    a: A. Inoue, K. Inoue* and A. Ito
    k: one-pebble Turing machines, two-way deterministic counter automata, alternation, universal states, sublogarithmically space-bounded computation
    c: Dept. of Comp. Sci. and Sys. Eng., Yamaguchi Univ., Yamaguchi 755-8611
    e: inoue@csse.yamaguchi-u.ac.jp
  4. Finding yozume of generalized tsume-shogi is EXPTIME-complete
    a: T. Yato*, T. Seta, T. Ito
    k: generalized Tsume-Shogi, yozume, EXPTIME-complete
    c: Dept. of Comp. Sci., Univ. of Tokyo., Tokyo, 113-0033
    e: yato@is.s.u-tokyo.ac.jp

COMPUTATIONAL LEARNING / KNOWLEDGE DISCOVERY

  1. Learning AC0 Boolean functions on attribute and label noise
    a: A. Miyata, J. Tarui, and E. Tomita*
    k: AC0, boolean function, noise, fourier coefficient
    c: Grad. school of Electro-Communications, Univ. of Electro-Communications, Tokyo 182-8585
    e: tomita@ice.uec.ac.jp
  2. Profile alignment with constraints
    a: T. Akutsu*, M. Hayashida, E. Tomita, J. Suzuki, and K. Horimoto
    k: bioinformatics, protein threding, profile alignment, maximum clique
    c: Inst. of Chemical Research, Kyoto Univ., Kyoto 611-0011
    e: takutsu@kuicr.kyoto-u.ac.jp
  3. Frequent substructure discovery from large unordered trees
    a: T. Asai*, S. Fusanobu, H. Arimura, T. Uno, and S. Nakano
    k: semistructured data, frequent pattern discovery, labeled unordered trees, Web mining, graph mining
    c: Dept. of Informatics, Kyushu University, Fukuoka 812-8581
    e: t-asai@i.kyushu-u.ac.jp
  4. Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data
    a: M. Wakatsuki*, K. Teraguchi, and E. Tomita
    k: learning from positive data, identification in the limit, polynomial time
    c: Dept. of Info. and Comm. Eng., Univ. of Electro-Communications, Tokyo 182-8585
    e: wakatuki@ice.uec.ac.jp
  5. On the PTF expression of Boolean functions
    a: K. Matsuo, T. Koyama, K. Amano, E. Takimoto* and A. Maruoka
    k: polynomial threshold functions, Fourier transformation, boosting, XOR-MDNF formulas, bent functions
    c: GSIS, Tohoku Univ., Miyagi 980-8579
    e: t2@ecei.tohoku.ac.jp
  6. Learning r-of-k threshold functions with boosting
    a: K. Hatano* and O. Watanabe
    k: boosting, AdaBoost, linear threshold function
    c: Dept. of Math. & Compt. Sci., Tokyo Tech, 152-8552
    e: hatano@is.titech.ac.jp

DISTRIBUTED COMPUTING

  1. A Pattern formation algorithm for distributed autonomous robots without agreements on axis orientations
    a: N. Yamanaka, N. Itoh, Y. Katayama , N. Inuzuka and K. Wada*
    k: distributed autonomous robots, pattern formation
    c: Dept. of Comp. Sci. and Eng., Grad. Sch. of Eng., Nagoya Institute of Technology, Aichi 466-8555
    e: wada@elcom.nitech.ac.jp
  2. Self-stabilizing edge coloring protocol resilient to Byzantine faults in tree networks
    a: Y. Sakurai, F. Ooshita, T. Masuzawa*
    k: fault containment
    c: Grad. Sch. of Info. Sci. and Tech., Osaka Univ., Osaka 560-8531
    e: masuzawa@ist.osaka-u.ac.jp
  3. A Super-stabilizing spanning tree protocol with route information
    a: T. Hasegawa, Y. Katayama* and N. Takahashi
    k: ad-hoc network, link failure
    c: Dept. of Comp. Sci. and Eng., Nagoya Institute of Tech., Aichi, 466-8555
    e: katayama@nitech.ac.jp
  4. A self-stabilizing protocol for mobile agent traversal with a node and link fault tolerance
    a: T. Nakamura, Y. Katayama* and N. Takahashi
    k: ad-hoc network
    c: Dept. of Elec. and Comp. Eng., Nagoya Institute of Tech., Aichi, 466-8555
    e: katayama@nitech.ac.jp
  5. Self-stabilizing shared heap supporting concurrent operations
    a: S. Asagoshi, Y. Nakaminami and T. Masuzawa*
    k: distributed system, fault tolerance, shared object
    c: Grad. Sch. of Inf. Sci. and Tech., Osaka Univ., Osaka 560-8531
    e: masuzawa@ist.osaka-u.ac.jp
  6. How to improve safety under convergence using stable storage
    a: J. Kiniwa
    k: self-stabilization, mutual exclusion, faulty privilege, vulnerability under convergence
    c: Dept. of Management Sci., Kobe Univ. of Commerce, Hyogo 651-2197
    e: kiniwa@kobeuc.ac.jp
  7. Performance guaranteed dynamic task scheduling of a parameter-sweep application onto a computational grid
    a: N. Fujimoto* and K. Hagihara
    k: approximation algorithm, grid computing
    c: Grad. Sch. of Info. Sci. and Tech., Osaka Univ., Osaka 560-8531
    e: fujimoto@ist.osaka-u.ac.jp
  8. Exact analyses of leader finding algorithms on unidirectional rings
    a: K. Kawakami and T. Shoudai*
    k: distributed algorithm, asynchronous rings
    c: Dept. of Informatics., Kyushu Univ., Fukuoka 816-8580
    e: shoudai@i.kyushu-u.ac.jp
  9. Neighborhood broadcasting in undirected de-Bruijn and Kautz networks
    a: S. Omura, Z. Hua and K. Wada*
    k: interconnection network
    c: Dept. of Comp. Sci. and Eng., Grad. Sch. of Eng., Nagoya Institute of Tech., Aichi 466-8555
    e: wada@elcom.nitech.ac.jp

FORMAL LANGUAGES AND AUTOMATA

  1. Three-way two-dimensional deterministic finite automata with rotated inputs
    a: H. Hirakawa, K. Inoue* and A. Ito
    k: Three-way two-dimensional deterministic finite automata, rotated inputs, accepting power
    c: Dept. of Comp. Sci. and Sys. Eng., Yamaguchi Univ., Yamaguchi 755-8611
    e: inoue@csse.yamaguchi-u.ac.jp
  2. Three-way two-dimensional alternating finite automata with rotated inputs
    a: H. Hirakawa, K. Inoue* and A. Ito
    k: three-way two-dimensional alternating finite automata, rotated inputs, accepting power
    c: Dept. of Comp. Sci. and Sys. Eng.,Yamaguchi Univ., Yamaguchi 755-8611
    e: inoue@csse.yamaguchi-u.ac.jp

QUANTUM COMPUTING

  1. On the design of an efficient quantum search algorithm on NMR quantum computers
    a: S. Okubo, T. Nishino*, N. Kunihiro and K. Ota
    k: quantum algorithms, NMR, Grover's algorithm
    c: Dept. of Info. and Comm. Eng., Univ. of Electro-Communications, Tokyo 182-8585
    e: nishino@ice.uec.ac.jp
  2. On quantum gates in decoherence-free subspaces
    a: Y. Kawano*, K. Kimura, and H. Sekigawa
    k: decoherence-free subspaces, error correction, Groebner bases, resultant
    c: NTT Communication Science Lab., NTT Co., Kanagawa 243-0198
    e: kawano@theory.brl.ntt.co.jp

SEMANTICS & TERM REWRITING SYSTEMS

  1. On computational models of priority rewriting systems
    a: K. Akitani*, T. Aoto and Y. Toyama
    k: term rewriting, priority rewriting, computational models
    c: RIEC, Tohoku Univ., Miyagi 980-8577
    e: akitani@nue.riec.tohoku.ac.jp