## Search

Now showing items 1-10 of 11

#### Ranking Cartesian Sums and K -maximum subarray problem

(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 ...

#### Theory of Trinomial Heaps

(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 ...

#### Improved Shortest Path Algorithms for Nearly Acyclic Graphs

(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 ...

#### Solving Shortest Paths Efficiently on Nearly Acyclic Directed Graphs

(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 ...

#### An O(n 3 log log n/ log n) Time Algorithm for the All-Pairs Shortest Path Problem

(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 ...

#### Theory of 2 - 3 heaps

(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 ...

#### Improved Shortest Path Algorithms for Nearly Acyclic Directed Graphs

(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 ...

#### Efficient Algorithms for the 2-Center Problems

(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 ...

#### An O(n 3 log log n/ log2 n) Time Algorithm for All Pairs Shortest Paths

(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 ...

#### Matrix Multiplication and All Pairs Shortest Paths

(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, ...