Efficient algorithms for certain graph theoretic problems

The thesis is primarily concerned with investigating efficient algorithms for several algorithmic problems related to graph theory and strings. In this thesis, we present several novel time/space-efficient algorithms as solutions to the following problems:

1. The gas station problem is concerned with finding the cheapest way for an agent with a limited fuel capacity to go from starting vertex s to a destination vertex d in a positively weighted graph where each node can have a gas station selling fuel at a certain price per unit and each positively weighted edge requires/consume the amount of fuel given by its distance/weight in order to be traversed. Note that the cheapest path between s and d is not always the shortest one. For this problem, we give an O(Δn2 + n2 log n) time algorithm improving an earlier result by Khuller et al. The techniques that we used in the solution may apply to a large class of recursive equations that are used with memoization/dynamic programming.

2. The fast delivery problem which requires finding the best possible way for k agents with different speeds in a n-node graph with m positively weighted edges to deliver a package at a certain node given that they can exchange the package both at nodes and at any point within edges. We provide an O(knlog(n) + km) time algorithm which at the time of writing the thesis is the state of art. The algorithm combines a modified SSSP algorithm with a method that finds the lower envelope of a set of points.

3. The ”All-Best-Swap-Edge”(ABSE) Problem on Tree Spanners is a problem concerned with finding the edge replacement with the minimum stretch factor in a tree σ-spanner of G, an n vertex unweighted graph for each possible edge removal in the original spanning tree. A σ-tree spanner of G is a spanning tree Tof G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by σ. The Stretch factor of a tree is the minimum value of σ for which T is a σ-tree spanner of G. We provide an O(n2) time and space algorithm for this problem.

At the moment of writing the thesis, all the algorithms are state-of-the-art solutions in terms of time complexity for their respective problems.