Neighborhood based algorithms for network problems

Abstract

This thesis presents novel techniques for designing efficient algorithms to solve various graph problems, with a focus on both sequential and parallel computation models. The key contributions include:

An O(dm)O(dm)O(dm) time algorithm for identifying hinge vertices in general graphs, where ddd is the maximum vertex degree and mmm is the number of edges. An O(1)O(1)O(1) time parallel algorithm for hinge vertex detection under the PRAM CRCW model. An O(dm)O(dm)O(dm) algorithm for detecting all cycles of length 4 in general graphs. An O(dm)O(dm)O(dm) algorithm for recognizing the largest value of kkk for which a graph is kkk-geodetically connected (k-GC), along with methods to construct sets of kkk-GC vertices and kkk-GEC edges. A parallel algorithm with O(log?log?n)O(\log \log n)O(loglogn) time complexity for recognizing geodetically connected graphs under the PRAM CRCW model.

These algorithms contribute to the advancement of graph theory by improving computational efficiency and enabling scalable parallel processing for complex graph structures.