Report on TGCOMP Meetings (Jan. - June, 2004)
This is a list of papers presented at TGCOMP meetings
held January - June of 2004.
-
TGCOMP is a Technical Group on foundation of Computing
under IEICE,
Institute for Electronics, Information and Communication Engineers of Japan.
TGCOMP organizes a meeting on TCS almost every month.
-
By O. Watanabe, 11/10/04.
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:
-
This list is compiled
from the information submitted to EATCS Japan Chapter by each presentater,
and though it covers almost all talks,
it is not the perfect one.
Also note that
the classification is made from my personal view point.
-
Please contact each author of the papers of your interest.
(I cannot answer to any question on each paper in the list!)
k = key words, a = author(s), c = address, and e = e-mail address.
ALGORITHMS: ON GRAPHS
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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.
-
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
-
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
-
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
-
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
-
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
-
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
-
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