Now showing items 1-17 of 17

    • Cascade Algorithm Revisited 

      Takaoka, Tadao; Umehara, Kiyomi (University of Canterbury, 2014)
      We revisit the cascade algorithm for the all pairs shortest path (APSP) problem. The operation on the distace data is limited to the triple operation of min{a, b + c}. The best known complexity on this model is n 3 by ...
    • Cascade algorithm revisited. 

      Takaoka, Tadao; Umehara, Kiyomi (University of Canterbury. Computer Science and Software Engineering, 2014)
      We revisit the cascade algorithm for the all pairs shortest path (APSP) problem. The operation on the distace data is limited to the triple oper- ation of min{a, b + c}. The best known complexity on this model is n3 by ...
    • Efficient Algorithms for the 2-Center Problems 

      Takaoka, Tadao (University of Canterbury, 2012)
      This paper achieves O(n 3 log log n/ log n) time for the 2- center problems on a directed graph with non-negative edge costs under the conventional RAM model where only arithmetic operations, branching operations, and ...
    • Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication 

      Takaoka, Tadao (University of Canterbury, 2002)
      We design an efficient algorithm that maximizes the sum of array elements of a subarray of a two-dimensional array. The solution can be used to find the most promising array portion that correlates two parameters involved ...
    • Improved Shortest Path Algorithms for Nearly Acyclic Directed Graphs 

      Tian, Lin; Takaoka, Tadao (University of Canterbury, 2012)
      This paper presents new algorithms for computing single source shortest paths (SSSPs) in a nearly acyclic directed graph G. The first part introduces higher-order decomposition. This decomposition is an extension of ...
    • Improved Shortest Path Algorithms for Nearly Acyclic Graphs 

      Saunders, Shane; Takaoka, Tadao (University of Canterbury, 2002)
      Dijkstra’s algorithm solves the single-source shortest path problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m ...
    • Matrix Multiplication and All Pairs Shortest Paths 

      Takaoka, Tadao (University of Canterbury, 2002)
      The all pairs shortest path (APSP) problem is to compute shortest paths between all pairs of vertices of a directed graph with non-negative real numbers as edge costs. We focus on shortest distances between veritices, ...
    • Minimal mergesort. 

      Takaoka, Tadao (University of Canterbury. Computer Science and Software Engineering, 1997)
      We present a new adaptive sorting algorithm, called minimal merge sort, which merges the ascending runs in the input list from shorter to longer, that is, merging the shortest two lists each time. We show that this algorithm ...
    • An O(n 3 log log n/ log n) Time Algorithm for the All-Pairs Shortest Path Problem 

      Takaoka, Tadao (University of Canterbury, 2004)
      We design a faster algorithm for the all-pairs shortest path problem under the conventional RAM model, based on distance matrix multiplication (DMM). Specifically we improve the best known time complexity of O(n 3 (log ...
    • An O(n 3 log log n/ log2 n) Time Algorithm for All Pairs Shortest Paths 

      Han, Yijie; Takaoka, Tadao (University of Canterbury, 2002)
      Given an input directed graph G = (V, E), the all pairs shortest path problem (APSP) is to compute the shortest paths between all pairs of vertices of G assuming that edge costs are real values. The APSP problem is a ...
    • Ranking Cartesian Sums and K -maximum subarray problem 

      Bae, Sung Eun; Takaoka, Tadao (University of Canterbury, 2006)
      We design a simple algorithm that ranks K largest in Cartesian sums X + Y in O(m + K log K ) time. Based on this, K -maximum subarrays can be computed in O(n + K log K ) time (1D) and O(n3 + K log K ) time (2D) for input ...
    • The Reverse Problem of Range Query. 

      Takaoka, Tadao (University of Canterbury, 2002)
      We dcsign an efficient algorithm for the problem of the two-dimensional range query. In the range query problem, we specify a range of a rectangular shape in a given (n, n) array, and munt the number of points in the range. ...
    • Shortest path algorithms for nearly acyclic directed graphs 

      Takaoka, Tadao (University of Canterbury. Computer Science and Software Engineering, 1997)
      Abuaiadh and Kingston gave an efficient algorithm for the single source shortest path problem for a nearly acyclic graph with O(m+n log t) computing time, where m and n are the numbers of edges and vertices of the given ...
    • Solving Shortest Paths Efficiently on Nearly Acyclic Directed Graphs 

      Saunders, Shane; Takaoka, Tadao (University of Canterbury, 2006)
      Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic ...
    • Sub-cubic cost algorithms for the all pairs shortest path problem. 

      Takaoka, Tadao (University of Canterbury. Computer Science and Software Engineering, 1997)
      In this paper we give three sub-cubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge ...
    • Theory of 2 - 3 heaps 

      Takaoka, Tadao (University of Canterbury, 2002)
      Abstract _ As alternati•m to ert, delet data structmre a 2-3 heap, opeTations in the 2-3 is the h&.p, a which ins log") ti e new data struc wide N)plication in graph Abstract _ As alternati•m to ert, delet data ...
    • Theory of Trinomial Heaps 

      Takaoka, Tadao (University of Canterbury, 2002)
      Abstract. we d ign a data structum , called which a in 0(1) an inært operation and a heap, is size of the heap. Th of trinomial Imp is it is æptaally and to tlw previously inve The Iwap is on binm•y linking, while is b on ...