Report on TGCOMP Meetings (Sept. - Dec, 2005)

This is a list of papers presented at TGCOMP meetings held on Sept., Oct., and Dec. of 2005. (Remark: Titles from the Dec. workshop are not presented, which will be fixed soon.)

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. The q-gram distance for ordered unlabeled trees
    a: N. Ohkura*, K. Hirata, T. Kuboyama, and M. Harao
    k: q-gram, q-gram distance, ordered unlabeled tree, depth sequence, postorder
    c: Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka, 820-8502
    e: ookura@dumbo.ai.kyutech.ac.jp
  2. An algorithm for generating vertex sequences to extract maximum weight cliques quickly
    a: K. Yamaguchi* and S. Masuda
    k: clique, branch-and-bound algorithm, upper bound, longest path
    c: Faculty of Engineering, Kobe University, Kobe 657-8501
    e: ky@kobe-u.ac.jp
  3. Queue layout of bipartite graph subdivisions
    a: M. Miyauchi
    k: bipartite graph, subdivision, queue, queue layout of graphs
    c: NTT Communication Science Laboratories, NTT Corporation, Kanagawa 243-0198
    e: miyauchi@theory.brl.ntt.co.jp
  4. Orthogonal drawings of series-parallel graphs with minimum bends
    a: Xiao Zhou* and T. Nishizeki
    k: orthogonal drawing, bend, series-parallel graph, planar graph
    c: Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579
    e: zhou@ecei.tohoku.ac.jp
  5. Convex drawings of plane graphs of minimum outer apices
    a: K. Miura, M. Azuma, and T. Nishizeki*
    k: graph drawing, convex drawing, minimum outer apices
    c: Fraduate School of Information Sciences, Tohoku University, Miyagi 980-8579
    e: nishi@ecei.tohoku.ac.jp
  6. On the graph orientation of minimizing the maximum outdegree
    a: Y. Asahiro*, E. Miyano, H. Ono, and J. Zenmyo
    k: graph orientation, min-max optimization, NP-hardness, approximation algorithms
    c: Dept. of Social Information Science, Kyushu Sangyo University, Fukuoka 813-8503
    e: asahiro@is.kyusan-u.ac.jp

ALGORITHMS: ON STRINGS

  1. A Polynomial space polynomial delay algorithm for enumerating maximal motifs in a sequence
    a: H. Arimura* and T. Uno
    k: enumeration algorithms, maximal motif discovery, basis of tiling motifs, bioinformatics
    c: Graduate School of Infomation Science and Technology, Hokkaido University, Sapporo 060-0814
    e: arim@ist.hokudai.ac.jp
  2. Compressing compressed data structures
    a: K. Sadakane* and R. Grossi
    k: data compression, succinct data structures
    c: Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka 812-8581
    e: sada@csce.kyushu-u.ac.jp

ALGORITHMS: ON SOME OTHER OBJECTS

  1. Automated competitive analysis of online problems
    a: T. Horiyama, K. Iwama*, and J. Kawahara
    k: online problems, online algorithms, competitive ratio, online knapsack problem
    c: Graduate School of Informatics, Kyoto University, Kyoto 606-8501
    e: imawa@kuis.kyoto-u.ac.jp
  2. An approximate algorithum for pricing European-Asian options
    a: T. Sekino, A. Shioura, and T. Tokuyama*
    k: options, Black-Scholes model, approximation algorithm, Trinomial model
    c: GSIS, Tohoku University, Miyagi 980-8579
    e: tokuyama@dais.is.tohoku.ac.jp

COMBINATORICS / PROBABILISTIC ANALYSIS

  1. Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs
    a: Y. Kikuchi* and T. Araki
    k: Bubble-sort, bipancyclic, edge-bipancyclic, hamiltonian cycle, fault-tolerance
    c: ERATO, Quantum Computation and Information Project, JST, Tokyo, 113-0033
    e: kikuchi@qci.jst.go.jp
  2. Laminar structure of ptolemaic graphs and its applications
    a: R. Uehara* and Y. Uno
    k: algorithmic graph theory, data structure, Hamiltonian cycle, intersection model, ptolemaic graph
    c: School of Information Science, JAIST, Asahidai 1-1, Nomi, Ishikawa, 923-1292
    e: uehara@jaist.ac.jp
  3. Hamiltonian laceability of bubble-sort graphs with edge faults
    a: A. Araki and Y. Kikuchi*
    k: bubble-sort graphs, hamiltonian laceability, strongly hamiltonian laceability, hyper hamiltonian laceability, hamiltonian cycle, fault-tolerance
    c: ERATO, Quantum Computation and Information Project, JST, Tokyo, 113-0033
    e: kikuchi@qci.jst.go.jp
  4. Monotone DNFs that minimize/maximize the number of satisfying assignments
    a: K. Amano*, T. Sato, and A. Maruoka
    k: DNF formula, satisfying assignments, counting, extremal combinatorics
    c: Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579
    e: ama@ecei.tohoku.ac.jp

COMPUTATIONAL COMPLEXITY / CRYPTOGRAPHY

COMPUTATIONAL LEARNING / KNOWLEDGE DISCOVERY

  1. How easy to learn linear ranking functions
    a: A. Nakamura
    k: linear ranking function, VC dimension, graph dimension, sample complexity
    c: Graduate School of Infomation Science and Technology, Hokkaido University, Sapporo 060-0814
    e: atsu@main.ist.kokudai.ac.jp
  2. Margin preserving projection with limited randomness and embedding to Boolean space
    a: T. Watanabe, E. Takimoto*, K. Amano, and A. Maruoka
    k: computational learning theory, computational geometry, random projection, k-wise independence, large margin classifier
    c: Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579
    e: t2@maruoka.ecei.tohoku.ac.jp
  3. Some sufficient conditions to solve the learning problem of simple deterministic languages from queries and counterexamples
    a: Y. Tajima, T. Koyani, and E. Tomita*
    k: grammatical inference, learning via queries, simple deterministic languages, live-complete set
    c: Dept. of Information and Communication Engineering, The University of Electro-Communications, Tokyo 182-8585
    e: tomita@ice.uec.ac.jp

DISTRIBUTED COMPUTING

  1. A weakly-adaptive condition-based consensus algorithm in asynchronous distributed systems
    a: T. Izumi* and T. Masuzawa
    k: asynchronous distributed system, consensus problem, fault tolerance, crash fault, condition-based approache
    c: Graduate Schoolf of Information Science and Technology, Osaka University, Osaka 560-8531
    e: t-izumi@ist.osaka-u.ac.jp

FORMAL LANGUAGES AND AUTOMATA

  1. A construction method of synchronous reversible cellular automata using simple asynchronous logic elements
    a: Jin-Shan QI and K. Morita*
    k: asynchronous logic circuit, delay-insensitive circuit, reversible cellular automaton
    c: Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527
    e: morita@iec.hiroshima-u.ac.jp
  2. An asynchronous cellular space in which synchronous reversible cellular automata can be embedded
    a: Jin-Shan Qi* and K. Morita
    k: asynchronous cellular automaton, block-to-block mapping, asynchronous logical element
    c: Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527
    e: qi@iec.hiroshima-u.ac.jp

QUANTUM COMPUTING

  1. A quantum protocol to win the graph colouring game on all Hadamard graphs
    a: David Avis, J. Hasegawa, Y. Kikuchi*, and Y. Sasaki
    k: graph colouring game, pseudo-telepathy, Hadamard graph, quantum chromatic number
    c: ERATO, Quantum Computation and Information Project, JST, Tokyo, 113-0033
    e: kikuchi@qci.jst.go.jp

SEMANTICS & TERM REWRITING SYSTEMS