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. Graph-theoretic algorithm for (2,3)-EC-SNDP
    a: H. Katsuya, T. Ono, and T. Hirata*
    k: survivable network design problem, depth first search, maximal spanning forest, edge connectivity
    c: Graduate School of Information Science, Nagoya University, Nagoya, 464-8603
    e: hirata@hirata.nuee.nagoya-u.ac.jp
  2. A Modified Greedy Algorithm for the Set Multicover Problem
    a: H. Kurahashi and T. Fujito*
    k: set multicover, approximation algorithm, simple b-edge cover
    c: Department of Information and Computer Sciences, Toyohashi University of Technology, Toyohashi 441-8580
    e: fujito@ics.tut.ac.jp
  3. Inferring Pedigrees from Genetic Distances
    a: T. Tamura, H. Ito, and K. Iwama*
    k: distance matrix, pedigree, genetic distance, phylogenetic tree, phylogenetic network
    c: School of Informatics, Kyoto University, Kyoto 606-8501
    e: iwama@kuis.kyoto.ac.jp
  4. Partitioning Graphs of Supply and Demand
    a: T. Ito, Xiao Zhou, and T. Nishizeki*
    k: algorithm, demand, maximum partition problem, partial k-trees, series-parallel graphs, supply
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: nishi@ecei.tohoku.ac.jp
  5. Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs
    a: K. Watanabe, S. Taoka, and T. Watanabe*
    k: partitioning problems, heuristic algorithms, optimal algorithms, demand, supply
    c: Graduate School of Engineering, Hiroshima University, Hiroshima, 739-8527
    e: watanabe@infonets,hiroshima-u.ac.jp
  6. Score Sequence Pair Problems of (r_{11},r_{12},r_{22})-Tournaments
    a: M. Takahashi, T. Watanabe, and T. Yoshimura*
    k: (r_{11},r_{12},r_{22})-tournament, score sequence pair, border sequence, basic sequence, turning point, judge point
    c: Graduate School of Waseda University, Fukuoka, 808-0135
    e: t-yoshimura@waseda.ac.jp
  7. Algorithms for Finding Distance-Edge-Colorings of Graphs
    a: T. Ito, A. Kato, X. Zhou, and T. Nishizeki*
    k: approximation algorithm, distance-edge-coloring, partial k-trees, planar graphs
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: nishi@ecei.tohoku.ac.jp
  8. Minimum 3-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Degree Constraints
    a: T. Mashima and T. Watanabe*
    k: graphs, edge-connectivity of a specified set of vertices, augmentation problems, degree constraints, linear time algorithms
    c: Graduate School of Engineering, Hiroshima University, Hiroshima, 739-8527
    e: watanabe@infonets.hiroshima.ac.jp
  9. A fast algorithms for calculating an upper bound of the weight of the maximum weighted clique
    a: K. Yamaguchi* and S. Masuda
    k: clique, branch-and-bound, vertex coloring, longest path
    c: Faculty of Engineering, Kobe University, Hyogo, 657-8501
    e: ky@kobe-u.ac.jp
  10. Lowering Eccentricity of a Tree by Node-Upgrading
    a: T. Ibaraki* and X.G. Yang
    k: communication network, eccentricity, node-upgrading
    c: School of Science and Technology, Kwansei Gakuin University, Hyogo, 669-1337
    e: ibaraki@ksc.kwansei.ac.jp
  11. Computing automorphism groups of chordal graphs whose simplicial components are of small size
    a: S. Toda
    k: chordal graph, simplicial component, automorphism group, graph isomorphism problem, algorithm, computational complexity
    c: Department of Computer Science and System Analysis, College of Humanities and Sciences, Nihon University
    e: toda@cssa.chs.nihon-u.ac.jp
  12. A Deterministic Algorithm for Finding All Minimum k-Way Cuts
    a: Y. Kamidoi, N. Yoshida, and H. Nagamochi*
    k: minimum cut, multiway cut, divide-and-conquer
    c: Dept. of Applied Mathematics and Physics, Kyoto University, Kyoto, 606-8501
    e: nag@amp.i.kyoto-u.ac.jp

ALGORITHMS: ON STRINGS

  1. Efficient Indexing and Updating of Text Databases
    a: T. Goto, H. Ono, K. Sadakane, and M. Yamashita*
    k: text database, string searching, compressed suffix array
    c: Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka, 812-8581
    e: mak@csce.kyushu-u.ac.jp
  2. Online and Dynamic Detection of Squares in Strings
    a: J. Jansson* and Z. Peng
    k: square, squarefree string, online algorithm
    c: Department of Computer Science, the University of Hong Kong, Hong Kong
    e: jjansson@cs.hku.hk

ALGORITHMS: ON-LINE ALGORITHMS

  1. Collect Tours for Moving Objects with Release Times and Deadlines
    a: Y. Asahiro, E. Miyano*, and S. Shimoirisa
    k: moving objects, collect tours, release times, deadlines
    c: Dept. of systems Innovation and Informatics, Kyushu Institute of Technology, Fukuoka, 820-8502
    e: miyano@ces,kyutech.ac.jp
  2. Online Allocation with Risk Information
    a: S. Harada, E. Takimoto, and A. Maruoka*
    k: online learning, resource allocation, Hedge algorithm, aggregating algorithm
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: maruoka@maruoka.ecei.tohoku.ac.jp
  3. Truthful Auctions with Limited Ranges of Bids
    a: D. Sumita, T. Horiyama, and K. Iwama*
    k: truthful auctions, algorithms, competitive ratios, limited ranges of bids
    c: Graduate School of Informatics, Kyoto University, Kyoto, 606-8501
    e: iwama@kuis.kyoto-u.ac.jp
  4. Improving Competitive Ratios of Online Buffer Management for Shared-Memory Switches
    a: K. Kobayashi*, S. Miyazaki, and Y. Okabe
    k: competitive analysis, shared memory switches, buffer management problem
    c: Graduate School of Informatics, Kyoto University, Kyoto, 606-8501
    e: kobaya@net.ist.i.kyoto-u.ac.jp

ALGORITHMS: ON SOME OTHER OBJECTS

  1. On Local Improvement Search for Weighted Set Packing
    a: M. Otake and T. Fujito*
    k: set packing, approximation algorithm, local search
    c: Department of Information and Computer Sciences, Toyohashi University of Technology, Aichi 441-8580
    e: fujito@ics.tut.ac.jp
  2. Guaranteed-Quality Anisotropic Mesh Generation for Parametric Surfaces
    a: Y. Yokosuka and K. Imai*
    k: anisotropic mesh generation, parametric surface, guaranteed-quality
    c: Faculty of Science and Engineering, Chuo University, Tokyo, 112-8551
    e: imai@ise.chuo-u.ac.jp
  3. Algorithms and Implementation of Peak-Reducing Fitting of a Curve
    a: M. Yuki, J. Chun, K. Sadakane, and T. Tokuyama*
    k: curve approximation complexity, peak-reduction, L_p-distance, unimodal approximation
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: tokuyama@dais.is.tohoku.ac.jp
  4. On Checkerboard Rounding: Theory and Implementation
    a: Y. Hirokawa and T. Tokuyama*
    k: digital halftoning, matrix rounding, discrepancy, algorithms
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: tokuyama@dais.is.tohoku.ac.jp
  5. Exact Algorithms for Two-Dimensional Strip Packing Problems
    a: M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura. and H. Nagamochi*
    k: strip packing, branch-and-bound, exact approach, perfect packing, sequence-pair
    c: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
    e: nag@amp.i.kyoto-u.ac.jp
  6. Branch-and-Bound Algorithms for MAX-2-SAT
    a: Y. Koga, K. Nonobe, M. Yagiura, H. Nagamochi*, and T. Ibaraki
    k: branch-and-bound, MAX-2-SAT, set covering problem
    c: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
    e: nag@amp.i.kyoto-u.ac.jp
  7. Hardness of Pickup and Delivery for Moving Objects on Broken Lines
    a: Y. Asahiro, E. Miyano*, and S. Shimoirisa
    k: moving objects, pickup and delivery, MAXSNP-hardness, approximation algorithm
    c: Dept. of Systems Innovation and Informatics, Kyushu Institute of Technology, Fukuoka, 820-8502
    e: miyano@ces.kyutech.ac.jp
  8. VSOP: Valued-Sum-Of-Products Calculator Based on Zero-Suppressed BDDs
    a: S. Minato
    k: BDDs, Zero-Suppressed BDDs, sum-of-products expressions
    c: Graduate School of Information Science and Technology, Hokkaido University, Hokkaido, 060-0814
    e: minato@ist.hokudai.ac.jp
  9. Objective Function Adjustment Algorithms for Combinatorial Optimization Problems
    a: H. Tamura, Z. Tang, and M. ishii*
    k: guided local search, Traveling Salesman Problems, objective function adjustment algorithm, tabu search
    c: Faculty of Engineering, Toyama University, Toyama, 930-8555
    e: ishii@iis.toyama-u.ac.jp
  10. Approximation Algorithms for Source Location Problems with Flow Requirements
    a: M. Sakashita, K. Makino, and S. Fujishige*
    k: location problem, connectivity, submodular function, set cover problem
    c: Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502
    e: fujishig@kurims.kyoto-u.ac.jp

COMBINATORICS / PROBABILISTIC ANALYSIS

  1. A lower bound for the vertex isoperimetric number of the complete k-ary trees
    a: Y. Otachi, K. Umezawa, and K. Yamazaki*
    k: vertex isoperimetric number, complete k-ary tree
    c: Department of Computer Science, Gunma University, Gunma, 376-8515
    e: koichi@comp.cs.gunma-u.ac.jp
  2. Recognition of Tree-Shellable Boolean Functions with Restrictions to the Number of the Same Literal
    a: N. Katougi and Y. Takenaga*
    k: Boolean function, binary decision tree, prime implicant, tree-shellability
    c: Department of Computer Science, Faculty of Electro-Communications, The University of Electro-Communications
    e: takenaga@cs.uec.ac.jp
  3. Improving a local search approximation algorithms for the stable marriage problem
    a: N. Yamaguchi, S. Miyazaki, and K. Iwama*
    k: the stable marriage problem, incomplete lists, ties, approximation algorithms, local search
    c: Graduate School of Informatics, Kyoto University, Kyoto, 606-8501
    e: iwama@lab2.kuis.kyoto-u.ac.jp
  4. Constant Time Generation of Linear Extensions
    a: O. Ono and S. Nakano*
    k: enumeration, algorithm, linear extension
    c: Faculty of Engineering, Gunma University, Gunma, 376-8515
    e: nakano@cs.gunma-u.ac.jp

COMPUTATIONAL COMPLEXITY

  1. Horn Functions with Single Two-negated Term
    a: N. Kawamura and S. Iwata*
    k: Horn functions, prime implicants, P-complete
    c: Department of Computer Science, The University of Electro-Communications, Tokyo, 182-8585
    e: iwata@np.cs.uec.ac.jp
  2. Energy Complexity of Threshold Circuits
    a: K. Uchizawa* and W. Maass
    k: neural networks, decision trees, energy complexity
    c: Graduate School of Information Sciences, Tohoku University, Miyagi, 980-8579
    e: uchizawa@maruoka.ecei.tohoku.ac.jp
  3. Complexity of coloring Comparability+ke Graphs
    a: K. Higashide and Y, Takenaga*
    k: comparability graph, graph vertex coloring problem, parameterized complexity
    c: Department of Computer Science, Faculty of Electro-Communications, The University of Electro-Communications, Tokyo, 182-8585
    e: takenaga@cs.uec.ac.jp
  4. NP-completeness of Maximum Chain Problem on Generalized Puyopuyo
    a: T. Matsukane and Y. Takenaga*
    k: NP-completeness, puzzle
    c: Faculty of Department of Computer Science, The University of Electro-Communications, Tokyo, 182-8585
    e: takenaga@cs.uec.ac.jp
  5. On time and space complexity of functions
    a: K. Ueno
    k: function complexity classes, recursive function theory, operators
    c: Department of Computer Science, Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 113-0033
    e: kenya@is.s.u-tokyo.ac.jp
  6. PUYOPUYO is NP-Complete
    a: H. Muta
    k: NP-Complete, Puzzle, 3-PARTITION
    c: Dept. of Computer Science, Graduate School of Information Science and Technology, University of Tokyo
    e: hmuta@is.s.u-tokyo.ac.jp
  7. A Method to Predict Computational Complexity of Adaptive Mesh Refinement by Fractal Analysis
    a: Y. Kawasaki*, F. Ino, and K. Hagihara
    k: adaptive mesh refinement, fractal geometry, computational complexity prediction
    c: Graduate School of Information Science and Technology, Osaka University, Osaka, 560-8531
    e: y-kawasak@ist.osaka-u.ac.jp

COMPUTATIONAL LEARNING / KNOWLEDGE DISCOVERY

  1. On the Complexity of Inferring a Graph from Path Frequency
    a: T. Akutsu* and D. Fukagawa
    k: graph inference, path frequency, pre-image, strongly NP-complete
    c: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto, 611-0011
    e: takutsu@kuicr.kyoto-u.ac.jp

CRYPTOGRAPHY

  1. RSA-based Public-Key Encryption Schemes with Anonymity
    a: R. Hayashi and K. Tanaka*
    k: RSA, anonymity, encryption, undeniable signature, confirmer signature, ring signature
    c: Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552
    e: keisuke@is.titech.ac.jp
  2. Hardness and an Approximation Algorithm for Minimum Certificate Dispersal Problems
    a: H. Zheng, S. Omura, and K. Wada*
    k: public-key based security system, certificate dispersal, approximation algorithm, NP-complete
    c: Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology, Aichi, 466-8555
    e: wada@nitech.ac.jp

DISTRIBUTED COMPUTING

  1. An Asynchronous Distributed Branch and Bound for Load Balancing
    a: A. Sasaki, T. Araragi, and S. Masuyama*
    k: discrete optimization, branch and bound, load balancing, integer programming
    c: Department of Knowledge-based Information Engineering, Toyohashi University of Technology, Aichi, 441-8580
    e: masuyama@tutkie.tut.ac.jp
  2. Performance Evaluation of PC Cluster-based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
    a: Y. Shimoda, S. Taoka, D. Takafuji, and T. Watanabe*
    k: parallel branch-and-bound algorithms, combinatorial optimization problems, MPI, optimum solutions
    c: Graduate School of Engineering, Hiroshima University, Hiroshima, 739-8527
    e: watanabe@infonets.hiroshima-u.ac.jp
  3. Algorithms for Map Labeling with Leader Lines
    a: K. Omori, S. Masuda, and K. Yamaguchi*
    k: labeling, leader line
    c: Faculty of Engineering, Kobe University, Hyogo, 657-8501
    e: ky@kobe-u.ac.jp

FORMAL LANGUAGES AND AUTOMATA

  1. Application of Parsing Trees to the Dictionary Editing System
    a: K. Narita and T. Kasai*
    k: machine translation, parsing tree, dictionary
    c: Graduate School of Electro-Communications, The University of Electro-Communications, Tokyo, 182-8585
    e: kasai@cs.uec.ac.jp
  2. Equality between Recognizable Expression and Finite Tree Automata
    a: F. Yamaguchi and K. Yamasaki
    k: finite state tree automata, recognizable set, recognizable expression
    c: Department of Information Sciences, Tokyo University of Science
    e: undef.
  3. Experimental Evaluation of Automata-based Algorithms for Matching Extended Regular Expressions
    a: H. Yamamoto
    k: extended regular expression, pattern matching algorithm, finite automata
    c: Faculty of Engineering, Shinshu University, Nagano, 380-8553
    e: yamamoto@cs.shinshu-u.ac.jp
  4. Similar Pattern Generation of Complex Snow Crystals Grown under Changing Environment
    a: K. Yamashita*, S. Hirose, Y. Ogoshi, and H. Kimura
    k: snow, crystal, similar pattern, cellular automaton
    c: Toyama University, Toyama, 930-8555
    e: k_yama@algo.iis.toyama-u.ac.jp
  5. The Relations among Watson-Crick Automata and Their Relations with Context-Free Languages
    a: S. Okawa and S. Hirose*
    k: DNA computer, Watson-Crick automata, formal languages, language family
    c: Toyama University, Toyama, 930-8555
    e: hirose@iis.toyama-u.ac.jp
  6. On Computational Power of Insertion-Deletion Systems without Using Contexts
    a: S. Hirose* and S. Okawa
    k: Insertion-Deletion system, DNA computing, formal language, automaton
    c: Toyama University, Toyama, 930-8555
    e: hirose@iis.toyama-u.ac.jp

QUANTUM COMPUTING

  1. A General Construction of Hard-Core Predicates for Any Quantum One-Way Function
    a: A. Kawachi* and T. Yamakami
    k: hard-core predicates, quantum one-way functions, quantum reduction, oracle identification problems
    c: Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552
    e: kawachi@is.titech.ac.jp
  2. Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups of Cyclic Groups
    a: Y. Inui* and F.L. Gall
    k: hidden subgroup problem, semi-direct product
    c: Department of Computer Science, Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 113-0033
    e: psi@is.s.u-tokyo.ac.jp

SEMANTICS & TERM REWRITING SYSTEMS

  1. AC-termination by modified monotonic AC-compatible semantic path orderings
    a: H. Ochiai, T. Aoto, and Y. Toyama*
    k: AC-term rewriting, AC-termination, AC-reduction order
    c: Research Institute of Electrical Communication, Tohoku University, Miyagi, 980-8577
    e: toyama@nue.riec.tohoku.ac.jp