Browsing College of Engineering by Author "Takaoka, Tadao"
Now showing items 117 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 2Center 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 nonnegative 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 twodimensional 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 higherorder 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 singlesource 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 nonnegative 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 AllPairs Shortest Path Problem
Takaoka, Tadao (University of Canterbury, 2004)We design a faster algorithm for the allpairs 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 twodimensional 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 1dominator set, which consists of a unique collection of acyclic ... 
Subcubic 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 subcubic 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 23 heap, opeTations in the 23 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 ...