University of Leicester
Browse

Efficient algorithms for certain graph theoretic problems

Download (541.6 kB)
thesis
posted on 2024-03-18, 10:24 authored by Kleitos Papadopoulos

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.

History

Supervisor(s)

Thomas Erlebach; Rajeev Raman

Date of award

2024-02-21

Author affiliation

School of Computing and Mathematical Sciences

Awarding institution

University of Leicester

Qualification level

  • Doctoral

Qualification name

  • PhD

Language

en

Usage metrics

    University of Leicester Theses

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC