Satoshi TAOKA


Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs
Satoshi TAOKA Daisuke TAKAFUJI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/06/01
Vol. E96-A  No. 6  pp. 1331-1339
Type of Manuscript:  Special Section PAPER (Special Section on Circuit, System, and Computer Technologies)
Category: 
Keyword: 
vertex coversminimum weight vertex cover problemapproximation algorithmscomputing experiment
 Summary | Full Text:PDF(1.5MB)

Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets
Satoru OCHIIWA Satoshi TAOKA Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/02/01
Vol. E96-A  No. 2  pp. 540-553
Type of Manuscript:  Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: Algorithms and Data Structures
Keyword: 
timed Petri netslegal firing sequence problemsdeficient siphonsheuristic algorithmsperformance evaluation
 Summary | Full Text:PDF(893.4KB)

A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
Tadachika OKI Satoshi TAOKA Toshiya MASHIMA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/03/01
Vol. E95-D  No. 3  pp. 769-777
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
connectivity augmentation problemsedge-connectivitybipartition constraintsgraphspolynomial time algorithms
 Summary | Full Text:PDF(341.7KB)

The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2011/09/01
Vol. E94-A  No. 9  pp. 1833-1841
Type of Manuscript:  PAPER
Category: Concurrent Systems
Keyword: 
Petri netsmarking construction problemreachability problemheuristic algorithmscomputer experiments
 Summary | Full Text:PDF(359.2KB)

FOREWORD
Satoshi TAOKA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/12/01
Vol. E93-A  No. 12  pp. 2708-2708
Type of Manuscript:  FOREWORD
Category: 
Keyword: 
 Summary | Full Text:PDF(89.4KB)

Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
Satoru OCHIIWA Satoshi TAOKA Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/11/01
Vol. E92-A  No. 11  pp. 2732-2744
Type of Manuscript:  Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Category: 
Keyword: 
Petri netslegal firing sequence problemsdeficient siphonsheuristic algorithmsperformance evaluation
 Summary | Full Text:PDF(460.9KB)

Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
Toshimasa WATANABE Satoshi TAOKA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/11/01
Vol. E92-A  No. 11  pp. 2707-2716
Type of Manuscript:  Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Category: INVITED
Keyword: 
Petri netsP-invariantsminimal supportssiphon-trapsFourier-Motzkin method
 Summary | Full Text:PDF(303.3KB)

Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
Satoshi TAOKA Daisuke TAKAFUJI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/04/01
Vol. E91-A  No. 4  pp. 1140-1149
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
parallel branch-and-bound algorithmscombinatorial optimization problemsMPIoptimum solutions
 Summary | Full Text:PDF(361.8KB)

Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
Daisuke TAKAFUJI Satoshi TAOKA Yasunori NISHIKAWA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/04/01
Vol. E91-A  No. 4  pp. 1129-1139
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
the maximum weight matching problem of graphsapproximate solutionsweight augmenting paths
 Summary | Full Text:PDF(490.7KB)

Performance Comparison of Algorithms for the Dynamic Shortest Path Problem
Satoshi TAOKA Daisuke TAKAFUJI Takashi IGUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/04/01
Vol. E90-A  No. 4  pp. 847-856
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
networksshortest pathsdynamic algorithmsstatic algorithmscomputational experiments
 Summary | Full Text:PDF(1.5MB)

Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs
Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/11/01
Vol. E89-A  No. 11  pp. 3216-3226
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: Concurrent Systems
Keyword: 
Petri netsinhibitor-arcslegal firing sequencespseudo-polynomial time algorithmsNP-hardness
 Summary | Full Text:PDF(447.3KB)

Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs
Satoshi TAOKA Kazuya WATANABE Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4  pp. 1049-1057
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphspartitioning problemsheuristic algorithmsoptimal algorithmsdemandsupply
 Summary | Full Text:PDF(437.2KB)

On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4  pp. 1042-1048
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsedge-connectivity of a specified set of verticesaugmentation problemsdegree constraintslinear time algorithms
 Summary | Full Text:PDF(325.4KB)

Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase
Toshiya MASHIMA Takanori FUKUOKA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/02/01
Vol. E89-D  No. 2  pp. 751-762
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
graphsvertex-connectivity of a specified set of verticesaugmentation problemsdegree constraintslinear time algorithms
 Summary | Full Text:PDF(624.1KB)

Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets
Satoshi TAOKA Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/11/01
Vol. E88-A  No. 11  pp. 3051-3061
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: 
Keyword: 
Petri netsminimal initial marking problemslegal firing sequence problemsdeficient siphonsheuristic algorithmsexperimental evaluation
 Summary | Full Text:PDF(394.9KB)

A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5  pp. 1290-1300
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphsaugmentation problemsedge-connectivityapproximation algorithms
 Summary | Full Text:PDF(389.2KB)

Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants
Akihiro TAGUCHI Atsushi IRIBOSHI Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Vol. E88-A  No. 4  pp. 964-971
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
Petri netsP-invariantsminimal supportssiphon-trapsFourier-Motzkin method
 Summary | Full Text:PDF(224.9KB)

A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase
Takanori FUKUOKA Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Vol. E88-A  No. 4  pp. 954-963
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsconnectivity augmentationvertex-connectivitydegree constraintslinear time algorithms
 Summary | Full Text:PDF(301.5KB)

A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
Makoto TAMURA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/04/01
Vol. E86-A  No. 4  pp. 822-828
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 15th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsaugmentation problemsvertex-connectivityperformance ratiospolynomial time algorithms
 Summary | Full Text:PDF(379.9KB)

Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants
Satoshi TAOKA Katsushi TAKANO Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/11/01
Vol. E85-A  No. 11  pp. 2436-2446
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
Category: 
Keyword: 
Petri netminimal siphon-trapsFourier-Motzkin methodinvariant computationpolynomial-time algorithms
 Summary | Full Text:PDF(494.1KB)

Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants
Katsushi TAKANO Satoshi TAOKA Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/11/01
Vol. E84-A  No. 11  pp. 2871-2880
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent Systems Technology)
Category: 
Keyword: 
Petri netminimal siphon-trapsFourier-Motzkin methodmemory overflow
 Summary | Full Text:PDF(766.1KB)

A Heuristic Algorithm FMDB for the Minimum Initial Marking Problem of Petri Nets
Shin'ichiro NISHI Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/03/01
Vol. E84-A  No. 3  pp. 771-780
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
Petri netminimal initial markingslegal firing sequencesdeficient siphons
 Summary | Full Text:PDF(427.1KB)

On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure
Toshihiro FUJITO Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/03/25
Vol. E83-A  No. 3  pp. 480-486
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 12th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
Petri netslegal firing sequence problempolynomial time algorithms
 Summary | Full Text:PDF(520.1KB)

A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph
Satoshi TAOKA Toshimasa WATANABE Kenji ONAGA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/03/25
Vol. E75-A  No. 3  pp. 410-424
Type of Manuscript:  Special Section PAPER (Special Section on the 4th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
linear-time algorithms3-edge-connected componentsdepth-first searchmultigraphs
 Summary | Full Text:PDF(978.8KB)