Alladi Ramakrishnan Hall

Parameterized Algorithms for some network design problems (THESIS DEFENCE)

Pranabendu Misra

University of Bergen Norway

In this thesis we design algorithms for several network design problems in
the framework of
parameterized complexity and exact algorithms.
​Such problems are very well studied in
approximation algorithms, but their parameterized complexity is relatively
unexplored.
Along the way, we also give deterministic
​ ​
algorithms for certain problems in matroid theory.
Our results adds to the small list of
​ ​
results on network design problems in the realm of
parameterized and exact algorithms
​.​ In particular we obtain the following results.

1. Single-exponential FPT algorithms and kernels for Augmenting the
Edge-connectivity of undirected graphs by one.
2. Single-exponential exact algorithms for Survivable Network Design with
uniform requirements.
3. Polynomial Kernel and FPT algorithm for Minimum Equivalent Digraph.
4. Single-exponential FPT algorithm for Eulerian Edge Deletion.
5. A deterministic polynomial time algorithm for computing representation
the truncation of a linear matroid.
6. Deterministic representation of Gammoids and Transversal matroids in
moderately exponential time.