Works and Papers


カウンター by  SOHO COUNTER

 

Enumeration and Counting

On listing, sampling, and counting the chordal graphs with edge constraints (corresponding author: Kijima) Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, and Takeaki Uno, Proceedings of COCOON2008, Lecture Notes in Computer Science 5092, pp. 458-467, 2008
Enumeration of Perfect Sequences of Chordal Graph (corresponding author: Uehara) Yasuko Matsui, Ryuhei Uehara, Takeaki Uno, Proceedings of ISAAC 2008, Lecture Notes in Computer Science 5369, pp. 859-870, 2008
Enumeration of Perfect Sequences of Chordal Graph (corresponding author: Uehara) Yasuko Matsui, Ryuhei Uehara, Takeaki Uno, 電気情報通信学会コンピューテーション研究会108, 信学技法 vol.108, no.11, pp.15-22, 2008
A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-Criteria Optimization (corresponding author: Okamoto) Yoshio Okamoto and Takeaki Uno, Proceedings of ISAAC 2007,  Lecture Notes in Computer Science 4835, Springer, pp.609-620, 2007
On the Enumeration of Bipartite Minimum Edge Colorings     power point  Yasuko Matsui, Takeaki Uno, Graph Theory in Paris, Proceedings of a Conference in Memory of Claude Berge,Trends in Mathematics, Birkhaeuser Boston Inc., pp.271-285, 2006
Listing Chordal Graphs and Interval Graphs (corresponding author: Kiyomi) Masashi Kiyomi, Shuji Kijima, Takeaki Uno, WG 2006, Lecture Notes in Computer Science 4271, pp. 68-77, 2006
Generating Chordal Graphs Included in Given Graphs (corresponding author: Kiyomi) Masashi Kiyomi, Takeaki Uno, Transactions on Information and Systems, IEICE, E89-D, No2, pp. 763-770, 2006
New Algorithms for Enumerating All Maximal Cliques      power point  Kazuhisa Makino, Takeaki Uno, Lecture Notes in Computer Science 3111 (SWAT2004, Scandinavia Workshop on Algorithm Theory), Springer-Verlag, pp.260-272
Generating Colored Trees (corresponding author: Nakano) Shin-ichi Nakano, Takeaki Uno, Wg2004, Lecture Notes in Computer Science 3787, pp. 249-260, Jun/2005.
Constant Time Generation of Trees with Specified Diameter       power point   (corresponding author: Nakano) Shin-ichi Nakano, Takeaki Uno, to appear Lecture Notes in Computer Science, Springer-Verlag
On the Enumeration of Colored Trees       power point    Shin-ichi Nakano, Takeaki Uno, 95th   SIGAL of Information Processing Sopciety Japan, 2004
A Simple Constant Time Enumeration Algorithm for Free Trees        power point  Shin-ichi NAKANO, Takeaki UNO, 91th   SIGAL of Information Processing Sopciety Japan, 2003
A Simple Algorithm for Generating Unordered Rooted Trees        power point    Shin-ichi NAKANO, Takeaki UNO, 90th   SIGAL of Information Processing Sopciety Japan, 2003
A Fast Algorithm for Enumeration of Maximal Matchings in General Graphs      power point  Takeaki Uno, Journal of National Institute of Informatics, Vol.3, pp. 89-97, 2001
An Optimal Algorithm for Scanning all Spanning Trees of Undirected Graphs (corresponding author: Shioura) Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno, SIAM Journal on Computing, Vol.26, No. 3, pp. 678-692, 1997
More Efficient Generation of Plane Triangulations        power point  Shin-ichi Nakano, Takeaki Uno, Lecture Notes in Computer Science 2912 (Graph Drawing 2003), Springer, pp.273-282, 2003
An Algorithm for Enumerating All Directed Spanning Trees in a Directed Graph Takeaki Uno, Lecture Note in Computer Science 1178, Springer-Verlag, Algorithms and Computation, (ISAAC96, International Symposium on Algorithm and Computation), pp. 166-173, 1996.

 

Schemes for Speeding up Enumeration Algorithms

Speeding Up Enumeration Algorithms with Amortized Analysis       power point  Takeaki Uno, 5th Workshop on Algorithms for Listing, Counting and Enumeration, 2003
A Fast Algorithm for Enumerating Bipartite Perfect Matchings        power point  Takeaki Uno, Lecture Note in Computer Science 2223 (International Symposium on Algorithm and Computation), Springer-Verlag, pp. 367-379, 2001
A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases Takeaki Uno, Lecture Note in Computer Science 1627, Springer-Verlag, (COCOON99, Computing and Combinatorics), pp. 349-359, 1999
A New Approach for Speeding Up Enumeration Algorithms Takeaki Uno, Lecture Note in Computer Science 1533, Springer-Verlag, (ISAAC98, International Symposium on Algorithm and Computation), pp. 287-296, 1998
Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs Takeaki Uno, Lecture Note in Computer Science 1350, Springer-Verlag, (ISAAC97, International Symposium on Algorithm and Computation), pp. 92-101, 1997
Studies on Speeding up Enumeration Algorithms Takeaki Uno, Doctoral thesis, Department of Systems Science, Tokyo Institute of Technology, JAPAN, Mar/1998

 

 

Algorithms for Large Scale Data (and Genome informatics)

 

Output Sensitive Algorithm for Finding Similar Objects      power point      Seminar talk on Combinatorial Algorithms Day in ETH Zurich

 

Mining complex genotypic features for predicting HIV-1 drug resistance (corresponding author: Saigo) Hiroto Saigo, Takeaki Uno, and Koji Tsuda, Bioinformatics 23, pp. 2455-2462,  2007
An Efficient Algorithm for Finding Similar Short Substrings from Large Scale String Data

typo:page6: for each i larger than the maximum integer in C do

=> for each i in c+1,...,k-d+c-|C| do (c= the maximum integer in C))

Takeaki Uno, PAKDD 2008, LNAI 5012, pp.345-356,  2008
Multi-Sorting Algorithm for Finding Pairs of Similar Short Substrings from Large Scale String Data

typo:page10: for each i larger than the maximum integer in C do

=> for each i in c+1,...,k-d+c-|C| do (c= the maximum integer in C))

Takeaki Uno, Knowledge and Information Systems, online published,  2009

 

Algorithms for Data Mining

 

Algorithmic Aspect of Frequent Pattern Mining and Its Extensions     power point      Seminar talk in Max Planc Institute Tuebingen, July/2007
Approach to Data Mining from Algorithm and Computation       power point        Seminar talk in Padova University, March/2006

 

Ambiguous Frequent Itemset Mining and Polynomial Delay Enumeration       power point  Takeaki Uno and Hiroki Arimura, Proceedings of PAKDD2008, Lecture Notes in Artificial Intelligence 5012, pp. 357-368, 2008
LCM over ZBDDs: Fast Generation of Very Large-Scale Frequent Itemsets Using a Compact Graph-Based Representation Shin-ichi Minato, Takeaki Uno, and Hiroki Arimura, Proceedings of PAKDD2008, Lecture Notes in Artificial Intelligence 5012, pp. 234-246, 2008
An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem Takeaki Uno, Algorithmica, Springer New York, 2008
An Efficient Algorithm for Enumerating Pseudo Cliques       power point  Takeaki Uno, Proceedings of ISAAC 2007,  Lecture Notes in Computer Science 4835, Springer, pp. 402-414, 2007
An Efficient Polynomial Delay Algorithm for  Pseudo Frequent Itemset Mining    power point  Takeaki Uno, and Hiroki Arimura, Lecture Notes in Artificial Intelligence 4755, (Proceeding of Discovery Science 2007), Springer, pp.219-230, 2007
Time and Space Efficient Discovery of Maximal Geometric Graphs (corresponding author: Arimura) Hiroki Arimura, Takeaki Uno, and Shinichi Shimozono, Lecture Notes in Artificial Intelligence 4755, (Proceeding of Discovery Science 2007), Springer, pp.42-55, 2007
Mining Maximal Flexible Patterns in a Sequence (corresponding author: Arimura) Hiroki Arimura, and Takeaki Uno, LLLL2007, Lecture Notes in Computer Science, Springer, 4914, pp. 307-317, 2008
Weighted Substructure Mining for Image Analysis (corresponding author: Nowozin) Sebastian Nowozin, Koji Tsuda, Takeaki Uno, Taku Kudo, Gökhan H. Bakir, MLG 2007
Weighted Substructure Mining for Image Analysis (corresponding author: Nowozin) Sebastian Nowozin, Koji Tsuda, Takeaki Uno, Taku Kudo, and Gökhan Bakir, CVPR 2007
An Efficient Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence (corresponding author: Arimura) Hiroki Arimura, Takeaki Uno, Journal of Combinatorial Optimization 13, pp.243-262, 2007
Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence (corresponding author: Arimura) Hiroki Arimura, Takeaki Uno, ISAAC2005, Lecture Notes in Computer Science 3827, pp. 724-737, 2005
An Output-Polynomial Time Algorithm for Mining Closed Frequent Ranked Tree Patterns (corresponding author: Arimura) Hiroki Arimura, Takeaki Uno, Lecture Notes in Artificial Intelligence 3625, (Proceeding of The 15th International Conference on Inductive Logic Programming), Springer, pp.1-19, Aug/2005
LCM ver.3: Collaboration of Array, Bitmap and Prefix Tree for   Frequent Itemset Mining        power point    Takeaki Uno, Masashi Kiyomi, Hiroki Arimura, Open Source Data Mining Workshop on Frequent Pattern Mining Implementations 2005, available at home page of Open Source Data Mining Workshop on Frequent Pattern Mining Implementations 2005, 21/Aug/2005
LCM ver.2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets        power point  Takiake Uno, Masashi Kiyomi, Hiroaki Arimura,  IEEE ICDM'04 Workshop FIMI'04 (International Conference on Data Mining, Frequent Itemset Mining Implementations)
An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases        power point    Takeaki Uno,Tatsuya Asai,Yuzo Uchida, Hiroki Arimura, Lecture Notes in Artificial Inteligence 3245 (Discovery Science 2004)
LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets         power point  Takeaki Uno and Tatsuya Asai, Hiroaki Arimura and Yuzo Uchida, IEEE ICDM'04 Workshop FIMI'03 (International Conference on Data Mining, Frequent Itemset Mining Implementations)
Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems        power point  Takeaki Uno and Tatsuya Asai, Hiroaki Arimura and Yuzo Uchida, 94th  SIGAL of Information Processing Sopciety Japan, 2004
Enumerating Minimal Explanations by Minimal Hitting Set Computation (corresponding author: Satoh) Ken Satoh, Takeaki Uno, KSEM 2006, Lecture Notes in Computer Science 4092, pp. 354-365, 2006
Contradiction Finding and Minimal Recover for UML class diagrams (corresponding author: Satoh) Ken Satoh, Ken Kaneiwa, Takeaki Uno, ASE2006, 2006
Enumerating Minimal Revised Specification using Dualization (corresponding author: Satoh) Ken, Satoh, Takeaki Uno, Workshop on Learning with Logics and Logics for Learning, Lecture Notes in Computer Science 4012, pp. 182-189, 2006
Detailed Description of an Algorithm for Enumeration of Maximal Frequent Sets with Irredundant Dualization        power point  Takeaki Uno and Ken Satoh, IEEE ICDM'03 Workshop FIMI'03 (International Conference on Data Mining, Frequent Itemset Mining Implementations)
Enumerating Maximal Frequent Sets using Irredundant Dualization (corresponding author: Satoh) Ken Satoh and Takeaki Uno, Lecture Notes in Artifical Intelligence 2843 (Discovery Science 2003), Springer-Verlag, pp. 255--267, 2003
Discovering Frequent Substructures in Large Unordered Trees       power point   (corresponding author: Asai) Tatsuya Asai and Hiroki Arimura and Takeaki Uno and Shin-ichi Nakano, Lecture Notes in Artifical Intelligence 2843 (Discovery Science 2003), Springer-Verlag, pp. 47-60, 2003

 

Scheduling and Vehicle Routing

An Iterated Local Search Algorithm for the Vehicle Routing  Problem with Convex Time Penalty Functions (corresponding author: Imahori) Toshihide Ibaraki, Shinji Imahori, Koji Nonobe, Kensuke Sobue, Takeaki Uno, Mutsunori Yagiura, Discrete Applied Mathematics 156, pp 458-467, 2008
Heuristic Approaches to the Capacitated Square Covering Problem  (corresponding author: Nonobe) Koji Nonobe, Endre Boros, Toshihide Ibaraki, Hiroya Ichikawa, Takeaki Uno, Mutsunori Yagiura, 6th Metaheuristics International Conference, Aug/2005
Effective Local Search Algorithms for Routing and Scheduling Problems with General Time Window Constraints  (corresponding author: Imahori) T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno and M. Yagiura, Transportation Science, Transportation Science, vol. 39, pp.206-232, 2005
An O(n^2 log^2n) Algorithm for Input-or-Output Test in Disjunctive Scheduling  (corresponding author: Miyamoto) Mikio Kubo, Yuichiro Miyamoto and Takiaki Uno, Journal of Operations Research Society of Japan, vol. 47, no.2, pp.112-122, 2004

 

Tree Algorithms

A Tree Partitioning Problem Arising from an Evacuation Problem in Tree Dynamic Networks (corresponding author: Mamada) Satoko Mamada, Takeaki Uno, Kazuhisa Makino and Satoru Fujishige, Journal of Operations Research Society Japan, Vol. 48, pp. 183-195, 2005  
An O(n log^2 n) Algorithm for the Optimal Sink Location Problem on Dynamic Tree Networks (corresponding author: Mamada) Satoko Mamada, Takeaki Uno, Kazuhisa Makino, Satoru Fujishige, IFIP TCS 2004, 25/Aug/2004
A Linear Time Algorithm for Finding a k-Tree Core Akiyoshi Shioura, Takeaki Uno, Journal of Algorithms, Vol.23, No.2, pp. 281-290, 1997.

 

Chemoinformatics

Algorithm for Advanced Canonical Coding of Planar Chemical Structures That  Considers Stereochemical and Symmetric Information (corresponding author: Koichi) Shungo Koichi, Satoru Iwata, Takeaki Uno, Hiroyuki Koshino and Hiroko Satoh, Journal of Chemical Information and Modeling 47, pp.1734-1746, 2007
Effective consideration of ring structures in CAST/CNMR  for highly accurate 13 C NMR chemical shift prediction (corresponding author: Satoh) Hiroko Satoh, Hiroyuki Koshino, Takeaki Uno, Shungo Koichi, Satoru Iwata and Tadashi Nakata, Tetrahedron 61, pp.7431-7437,  2005

 

Graph Algorithms

Partitioning a Weighted Tree to Subtrees of Almost Uniform Size (corresponding author: Ito) Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki, Proceedings of ISAAC 2008, Lecture Notes in Computer Science 5369, pp. 196-207, 2008
Counting the Number of Independent Sets in Chordal Graphs (corresponding author: Okamoto) Yoshio Okamoto, Ryuhei Uehara, and Takeaki Uno, Journal of Discrete Algorithms, 2007
Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs (corresponding author: Uehara) Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara, WG2004, Lecture Notes in Computer Science 3787, pp. 433-444, Jun/2005.
A New Approach to Graph Recognition and Applications to Distance Hereditary Graphs (corresponding author: Uehara) Shin-ishi Nakano, Ryuhei Uehara and Takeaki Uno, Lecture Notes in Computer Science 4484   (Proceedings of TAMC 2007), pp. 115-127, 2007

 

Other Algorithms

Improved Bounds for Wireless Localization (corresponding author: Christ) Tobias Christ, Michael Hoffmann, Yoshio Okamoto, Takeaki Uno, Proceedings of SWAT2008, Lecture Notes in Computer Science 5124, pp. 77-89, 2008.
Efficient Algorithms for Airline Problem (corresponding author: Uehara) Shin-ishi Nakano, Ryuhei Uehara and Takeaki Uno, Lecture Notes in Computer Science 4484  (Proceedings of TAMC 2007), pp. 428-439, 2007
Polynomial Time Algorithms for Maximizing the Intersection Volume of Polytopes Komei Fukuda and Takeaki Uno, Pacific Journal on Optimization 3, No.1, pp. 37-52, 2007
Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps (corresponding author: Benkert) Marc Benkert, Martin Noellenburg, Takeaki Uno, Alexander Wolff, GD2006, Lecture Notes in Computer Science 4372, pp. 270-281, 2007
Efficient Algorithms for the Electric Power Transaction Problem (corresponding author: Kiyomi) Masashi Kiyomi, Takeaki Uno, Tomomi Matsui, WINE 2005, Lecture Notes in Computer Scinence 3828, pp. 602-611, 2005
Labeling points with weights (corresponding author: Wolff) Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, Takeaki Uno, and Alexander Wolff, to appear Algorithmica.
A Short Note on the Reducibility of the Collapsing Knapsack Problem (corresponding author: Iida) Hiroshi Iida, Takeaki Uno, Journal of Operations Research Society of Japan, Vol.45, 2002
A Cutting Plane Algorithm for Semi-Definite Programming Problems with Applications to Failure Discrimination and Cancer Diagnosis  (corresponding author: Goto) Hiroshi KONNO, Jun-ya GOTO, Takeaki UNO, to appear in Journal of Computational and Applied Mathematics.
Fast Algorithms to Enumerate All Common Intervals of Two Permutations   (corresponding author: Yagiura) Takeaki Uno, Mutsunori Yagirura, Algorithmica, Vol. 26, pp. 290-309, 2000

 

Other Topics

Matroid Representation of Clique Complexes (corresponding author: Okamoto) Kenji Kashiwabara,Yoshio Okamoto, and Takeaki Uno, Discrete Applied Mathematics 155, No. 15, pp 1910-1929, 2007
Matroid Representation of Clique Complexes (corresponding author: Okamoto) Kenji Kashiwabara, Yoshio Okamoto and Takeaki Uno, Lecture Notes in Computer Science 2697 (International Computing and Combinatorics Conference, COCOON 2003 ), Springer-Verlag, pp. 192-201, 2003
A Generalization of Magic Squares with Applications to Digital  Halftoning (corresponding author: Asano) Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, and Takeaki Uno, Theory of Computing Systems, 2007
Towards Knowledge-Based Affective Interaction : Situational   Interpretation of Affect (corresponding author: Abbasi) Abdul Rehman Abbasi, Takeaki Uno, Matthew N. Dailey, and Nitin V.  Afzulpurkar, 2nd International Conference on ACII 2007, 2007
Transforming Spanning Trees: A Lower Bound (corresponding author: Buchin) Kevin Buchin, Andreas Razen, Takeaki Uno, Uli Wagner, 23nd European Workshop on Computational Geometry, 2007
A Generalization of Magic Squares with Applications to Digital Halftoning (corresponding author: Asano) Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno, Lecture Notes in Computer Science (Proceedings of ISAAC 2004), pp. 89-100, 2004
Generalized Amazons is PSPACE-Complete (corresponding author: Furtak) Timothy Furtak, Masashi Kiyomi, Takeaki Uno, Michael Buro, 19th International Joint Conference on Artificial Intelligence, pp. 132-137, Aug/2005

 

 

 Uno's Homepage          NII Homepage