Efficient algorithms for certain graph theoretic problems

<p>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:</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p>