## Search

Now showing items 1-10 of 11

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

#### Cascade Algorithm Revisited

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

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

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

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

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

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

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