Academic Activity
[Research Interest]
My research interest is the connectivity augmentation problem of a graph which is one of the combinatorial optimization problems. In particular, we developed fast algorithms for augmenting edge-connectivity by one with partition constraints. The algorithms are based on the property of the cactus which represents all minimum cuts in a given graph.
[Papers] (2018/02/01 updated)
1. Satoshi Taoka, Tadachika Oki, Toshiya Mashima, and Toshimasa Watanabe,
Reduction of Constraints from Multipartition to Bipartition in Augmenting Edge-Connectivity of a Graph by One,
IEICE Trans. Fundamentals, Vol. E101-A, No.2, pp. 357-366, 2018. [ J-STAGE, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences ]
2. Tadachika Oki, Satoshi Taoka, Toshiya Mashima, and Toshimasa Watanabe,
A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints,
IEICE Trans. Information and Systems, Vol. E95-D, No. 3, pp.769-777, 2012. [ J-STAGE, IEICE Transactions on Information and Systems ]
[Talks in International Conferences]
1. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Simplified Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints,
The First International Workshop on Networking, Computing, Systems, and Software (NCSS), 2011 (non-refereed).
[ Bulletin of Networking, Computing, Systems, and Software ]
2. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Fast Algorithm for Augmenting Edge-Connectivity by One with Multipartition Constraints,
The 26th International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC), 2011 (poster session).
3. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Parallel Algorithm for 2-Edge-Connectivity Augmentation of a Connected Graph with Multipartition Constraints,
2nd International Workshop on Parallel and Distributed Algorithms and Applications (PDAA), 2010.
[ IEEE Computer Society, CS Digital Library ]
[Talks in Domestic Conferences (in Japanese)]
1. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Fast Algorithm for (σ + 1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints,
IPSJ SIG Technical Report Vol.2010-AL-131 No.10, September 2010. [ CiNii ]
2. Tadachika Oki, Satoshi Taoka, Toshiya Mashima, Toshimasa Watanabe,
A fast algorithm for (σ+ 1)-edge-connectivity augmentation of a σ-edge connected bipartite graph,
In Proceeding of the 23th Karuizawa Workshop on Circuits and Systems, pp 404-409, 2010.
3. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Fast Algorithm for (k + 1)-Edge-Connectivity Augmentation of a k-Edge-Connected Bipartite Graph,
IPSJ SIG Technical Report Vol.2010-AL-129 No.7, March 2010. [ CiNii ]
4. Tadachika Oki, Satoshi Taoka, Toshimasa Watanabe,
A Meta-System Maintaining Specification Consistency for Generating Web Systems,
IEICE technical report. Office Information Systems 106(582),pp 13-18, 20070302. [ CiNii ]