UC Spark

Professor Tad Takaoka

Computer Science and Software Engineering

Fields of Research

  • Maximum subarray problem
  • Algorithms
  • Approximate pattern matching
  • Combinatorial generation
  • Shortest paths

Researcher Summary

Research interests include algorithms, approximate pattern matching, shortest paths. The main purpose of the research is to design efficient algorithms for the above mentioned problems.

Subject Area: Disciplines

Research Groups

Future Research

  • Speed-up of algorithms for the maximum sub-array problem
  • Combinatorial generation for multi-set permutations and combinations
  • Algorithms for the all pairs shortest path problem

Key Methodologies

  • Algorithm analysis
  • Performance measurement

Affiliations

Prizes and Awards

  • College of Engineering Research Award (2007)
  • Erskine Grant (11/12/00-16/01/01). Nat.U.Singapore, Uni's of Hong Kong, Kyoto, Ritsumeikan, Kansai, Academia Sinica Taipei (2001)

Research Service

  • External examiner for a PhD thesis at Auckland University in June 2007. (2007)
  • I supervised three Ph. D students as main supervisor, supervised a Ph. D student as co-supervisor and five masters students as main supervisor. (2006-present)
  • Organizing chair of the 12th International Symposium on Algorithms and Computation (ISAAC 2001), held in Christchurch (2001)

Publications


  • Takaoka, T. (2013) A simplified algorithm for the all pairs shortest path problem with O(n^2logn) expected time. Journal of Combinatorial Optimization 25(2): 326-337. http://dx.doi.org/10.1007/s10878-012-9550-3. (Journal Article)
  • Han, Y. and Takaoka, T. (2012) An O(n^3 loglogn/log^2 n) Time Algorithm for All Pairs Shortest Paths. Helsinki, Finland: 13th Scandinavian Symposium and Workshops (SWAT), 4-6 Jul 2012. In Lecture Notes in Computer Science (LNCS) 7357(Algorithm Theory - SWAT 2012:) 131-141. http://dx.doi.org/10.1007/978-3-642-31155-0_12. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2012) Efficient Algorithms for the All Pairs Shortest Path Problem with Limited Edge Costs. Melbourne, Australia: Eighteenth Computing: The Australasian Theory Symposium (CATS 2012), 1-5 Feb 2012. In CRPIT 128: 21-26. http://crpit.com/confpapers/CRPITV128Takaoka T..pdf. (Conference Contribution - Paper in published proceedings)
  • Thaher, M. and Takaoka, T. (2012) Improved algorithms for the K overlapping maximum convex sum problem. Omaha, NE, USA: International Conference on Computational Science (ICCS), 4-6 Jun 2012. In Procedia Computer Science 9(2012:) 754-763. http://dx.doi.org/10.1016/j.procs.2012.04.081. (Conference Contribution - Paper in published proceedings)
  • Thaher, M. and Takaoka, T. (2011) An efficient algorithm for computing the K-overlapping maximum convex sum problem. Singapore: International Conference on Computational Science (ICCS 2011), 1-3 Jun 2011. In Procedia Computer Science 4 1288-1295. http://dx.doi.org/10.1016/j.procs.2011.04.139. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. and Hashim, M. (2011) Sharing Information in All Pairs Shortest Path Algorithms. Perth, Australia: Seventeenth Computing: The Australasian Theory Symposium (CATS 2011), 17-20 Jan 2011. In Conferences in Research and Practice in Information Technology 119 131-136. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. and Hashim, M. (2010) A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n^2log n) Expected Time. The Big Island, HI, USA: 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010), 18-20 Dec 2010. In Proceedings of the 4th international conference on Combinatorial optimization and applications - Part II (Conference Contribution - Paper in published proceedings)
  • Thaher, M. and Takaoka, T. (2010) An efficient algorithm for the k maximum convex sums. University of Amsterdam, The Netherlands: International Conference on Computational Science (ICCS 2010), 31 May-2 Jun 2010. In Procedia Computer Science 1(1) 1475-1483. http://dx.doi.org/10.1016/j.procs.2010.04.163. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2010) Efficient Algorithms for the 2-Center Problems. Kyushu Sangyo University, Fukuoka, Japan: 2010 International Conference on Computational Science and its Applications (ICCSA 2010), 23-26 Mar 2010. In Lecture Notes in Computer Science (LNCS) 6017 519-531. http://dx.doi.org/10.1007/978-3-642-12165-4_41. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. and Nakagawa, Y. (2010) Entropy as Computational Complexity. Journal of Information Processing 18: 227-241. (Journal Article)
  • Takaoka, T. (2009) Partial Solution and Entropy. Nový Smokovec, Slovakia: 34th International Symposium on Mathematical Foundations of Computer Science (MFCS 2009), 24-28 Aug 2009. In Lecture Notes in Computer Science 5734 700-711. http://dx.doi.org/10.1007/978-3-642-03816-7_59. (Conference Contribution - Paper in published proceedings)
  • Bae, S.E. and Takaoka, T. (2007) A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem. Sendai, Japan: 18th International Symposium on Algorithms and Computation (ISAAC 2007), 17-19 Dec 2007. In Lecture Notes in Computer Science 4835, 751-762. (Conference Contribution - Paper in published proceedings)
  • Bae, S.E. and Takaoka, T. (2007) Algorithms for K-Disjoint Maximum Subarrays. International Journal of Foundations of Computer Science 18(2): 319-339. http://dx.doi.org/10.1142/S012905410700470X. (Journal Article)
  • Fukuda, K. and Takaoka, T. (2007) Analysis of Air Pollution (PM10) and Respiratory Morbidity Rate using K-Maximum Sub-array (2-D) Algorithm. Seoul, Korea: 2007 ACM Symposium on Applied Computing (SAC 2007), 11-15 Mar 2007. In Proceedings of the 2007 Symposium on Applied Computing 153-157. http://doi.acm.org/10.1145/1244002.1244041. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. and Violich, S. (2007) Fusing Loopless Algorithms for Combinatorial Generation. International Journal of Foundations of Computer Science 18(2): 263-293. http://dx.doi.org/10.1142/S0129054107004681. (Journal Article)
  • Fukuda, K. and Takaoka, T. (2007) Investigation of the Maximum Association for Suicide Rate and Social Factors Using Computer Algorithm. Christchurch, New Zealand: MODSIM 2007 International Congress on Modelling and Simulation, 10-13 Dec 2007. In MODSIM 2007 International Congress on Modelling and Simulation Proceedings 2882-2888. http://mssanz.org.au/MODSIM07/papers/52_s24/Investigations24_Fukuda_.pdf. (Conference Contribution - Paper in published proceedings)
  • Saunders, S. and Takaoka, T. (2007) Solving shortest paths efficiently on nearly acyclic directed graphs. Theoretical Computer Science 370(1-3): 94-109. http://dx.doi.org/10.1016/j.tcs.2006.10.008. (Journal Article)
  • Kiriyama, A., Nakagawa, Y., Takaoka, T. and Tu, Z. (2006) A new public-key cryptosystem and its applications. Paphos, Cyprus: 8th International Conference on Enterprise Information Systems (ICEIS 2006), 23-27 May 2006. In Proceedings of the Eighth International Conference on Enterprise Information Systems: Databases and Information Systems Integration 534-537. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T., Pope, N.K.L. and Voges, K.E. (2006) Algorithms for Data Mining. In K. Voges and N. Pope (Ed.), Business Applications and Computational Intelligence: 291-315. Hershey: Idea Group Inc. (Chapter in Book)
  • Bae, S.E. and Takaoka, T. (2006) Algorithms for K Disjoint Maximum Subarrays. Reading, UK: International Conference on Computational Science (ICCS 2006): Advancing Science through Computation, 28-31 May 2006. In Lecture Notes in Computer Science 3994, 595-602. http://dx.doi.org/10.1007/11758501_80. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. and Violich, S. (2006) Combinatorial Generation by Fusing Loopless Algorithms. Hobart, Australia: Computing: The Australasian Theory Symposium (CATS 2006), 16-19 Jan 2006. In Theory of Computing 2006. Proceedings of the Twelfth Computing: The Australasian Theory Symposium (CATS2006) 69-77. (Conference Contribution - Paper in published proceedings)
  • Saunders, S. and Takaoka, T. (2005) Efficient Algorithms for Solving Shortest Paths on Nearly Acyclic Directed Graphs. Newcastle: 2005 Australasian Symposium on Theory of Computing (CATS '05), 2005. In Conferences in Research and Practice in Information Technology 41 127-131. http://dl.acm.org/citation.cfm?id=1082275. (Conference Contribution - Paper in published proceedings)
  • Bae, S.E. and Takaoka, T. (2005) Improved Algorithms for the K-Maximum Subarray Problem for Small K. Kunming, China: Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, 16-19 Aug 2005. In Lecture Notes in Computer Science 3595(2005) 621-631. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2004) A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application. Jeju Island, Korea: Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, 17-20 Aug 2004. In Lecture Notes in Computer Science 3106(2004) 278-289. (Conference Contribution - Paper in published proceedings)
  • Bae, S.E. and Takaoka, T. (2004) Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem. Hong Kong: International Symposium on Parallel Architectures, Algorithms and Networks, ISPAN 2004, Apr 2004. 247-253. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2004) Foreword. Allgorithmica 38(2): 269-270. (Journal Article)
  • Saunders, S. and Takaoka, T. (2003) Improved shortest path algorithms for nearly acyclic graphs. Theoretical Computer Science 293(3): 535-556. (Journal Article)
  • Bae, S. and Takaoka, T. (2003) Parallel approaches to the maximum subarray problem. Sendai, Japan: Proceedings of the Japan-Korea Workshop on Algorithms and Computation, 3-4 Jul 2003. 94-104. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2003) The Reverse Problem of Range Query. Adelaide: Proceedings of CATS 2003 (Computing: the Australasian Theory Symposium, Electronic Notes in Computer Science, vol 78), 4-7 Feb 2003. In Electronic Notes in Computer Science 78 (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (2003) Theory of 2-3 Heaps. Discrete Applied Mathematics 126(1): 115-128. (Journal Article)
  • Takaoka, T. (2002) Efficient Algorithms for the maximum subarray problem by distance matrix multiplication. Melbourne: Proceedings of CATS (Computing: the Australasian Theory Symposium, Electronic Notes in Computer Science), Jan 2002. (Conference Contribution - Paper in published proceedings)
  • Saunders, S. and Takaoka, T. (2001) Improved Shortest Path Algorithms for Nearly Acyclic Graphs. Gold Coast: The Australasian Theory Symposium, 2001. In Proceedings of Computing: The Australasian Theory Symposium 42 232-248. (Conference Contribution - Paper in published proceedings)
  • Eades, P. and Takaoka, T. (2001) International Symposium on Algorithms and Computation (ISAAC'01), volume 2223 of Lecture Notes in Computer Science. Berlin: Springer. (Authored Book)
  • Takaoka, T. (2000) Theory of Trinomial Heaps. Sydney, Australia: Computing and Combinatorics: 6th Annual International Conference, COCOON 2000, Jul 2000. In Lecture Notes in Computer Science 1858(2000) 362-372. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (1999) An O(1) Time Algorithm for Generating Multiset Permutations, ISAAC '99, Lecture Notes in Computer Science. Madras: ISAAC 99, 1999. 1741., 237--46.. (Conference Contribution - Full conference paper)
  • Sprague, A. and Takaoka, T. (1999) O(1) Query Time for the All Pairs Shortest Distances on Interval Graphs. International Journal of Foundations of Computer Science 10(4): 473--482. (Journal Article)
  • Takaoka, T. (1999) O(1) Time Algorithms for Combinatorial Generation by Tree Traversal. The Computer Journal 42(4): 401--408. (Journal Article)
  • Takaoka, T. (1999) Theory of 2-3 heaps. Tokyo, Japan: COCOON '99, Lecture Notes in Computer Science, 'July 1999'. In Lecture Notes in Computer Science, Springer-Verlag 1627 41-50. (Conference Contribution - Paper in published proceedings)
  • Takaoka, T. (1998) A new measure of disorder - entropy. Perth: In Fourth Australasian Theory Symposium, CATS '98, 1998. 77--85.. (Conference Contribution - Full conference paper)
  • Takaoka, T. (1998) Shortest path algorithms for nearly acyclic directed graphs. Theoretical Computer Science 203: 143--150. (Journal Article)
  • Takaoka, T. (1998) Subcubic cost algorithms for the all pairs shortest path algorithms. Algorirhmica 20: 309--18. (Journal Article)
  • Mikawa, K. and Takaoka, T. (1997) Generation of Parenthesis Strings by Transpositions. Sydney, Australia: CATS 97, Computing: the Australasian Theory Symposium, February 1997. (Conference Contribution - Full conference paper)
  • Takaoka, T. (1997) 'Shortest Path Algorithms for Nearly Acyclic Directed Graphs', Graph-Theoretic Concepts in Computer Science (WG 97), Lecture Notes in Computer Science. Cadenabbia, Italy: Graph-Theoretic Concepts in Computer Science, June, 1996. In Lecture Notes in Computer Science, Springer-Verlag 1197 367--374.. (Conference Contribution - Full conference paper)
  • Takaoka, T. (1996) A Left-to-Right Computation of the DD-Table in the Boyer-Moore String Matching Algorithm. Computer Journal 39(5): 413 - 416. (Journal Article)
  • Gu, Q. P. and Takaoka, T. (1996) A Parallel Algorithm for the Longest Path Problem for Acyclic Graphs with Integer Arc Lengths. Transactions of the Information Processing Society of Japan 37(9): 1631 - 1636. (Journal Article)
  • Takaoka, T. (1996) A systematic approach to parallel program verification. Transactions of the Information Society of Japan 37: 1244 - 1254. (Journal Article)
  • Ma, J., Takaoka, T. and Ma, S. (1994) A Parallel Algorithm for Graph Problems. Transactions of the Information Processing Society of Japan 35(7) (Journal Article)
  • Takaoka, T. (1992) A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem. Information Processing Letters 43: 195 - 199. (Journal Article)
  • Takaoka, T. and Umehara, K. (1992) An Efficient VLSI Algorithm for the All Pairs Shortest Path Problem. Journal of Parallel and Distributed Computing, 16: 265 - 272. (Journal Article)
  • Gu, Q.P. and Takaoka, T. (1990) A Sharper Analysis of a Parallel Algorithm for the All Pairs Shortest Path Problem. Parallel Computing 16(1): 61 - 67. (Journal Article)
  • Dey, P., Bryant, B.R. and Takaoka, T. (1990) Lexical Ambiguity in Tree Adjoining Grammars. Information Processing Letters 34(2): 65 - 69. (Journal Article)
  • Zhu, R.F. and Takaoka, T. (1989) A Technique for Two Dimensional Pattern Matching. Communications of the ACM 32(9): 1110 - 1120. (Journal Article)