PhD Oral Exam - Narek Hovhannisyan, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

Broadcasting is one of the fundamental information dissemination primitives in interconnection networks, where a message is passed from one node (called originator) to all other nodes in the network. Following the increasing interest in interconnection networks, extensive research was dedicated to broadcasting. Two main research goals of this area are finding inexpensive network structures that maintain efficient broadcasting and finding the broadcast time for well-known and widely used network topologies. In the scope of this study, we will mainly focus on determining the broadcast time and near-optimal broadcasting schemes in networks. Determination of the broadcast time of any node in an arbitrary network is known to be NP-hard. Polynomial time solutions are known only for a few network topologies. There also exist various heuristic and approximation algorithms for different network topologies. In this study, we consider the minimum broadcast time problem on different network topologies and settings.

We begin by studying the broadcast time problem on split graphs. First, we introduce a tight polynomial-time constant approximation algorithm for broadcasting on split graphs. Then, we thoroughly study some important characteristics of an optimal broadcast scheme on split graphs, which help us to design a strategy for generating optimal broadcast schemes. We apply our findings to devise an efficient broadcasting heuristic on split graphs. We also study a natural generalization of split graphs, called (k, l)-graphs. We extend the split graph heuristic to (k, l)-graphs and empirically analyze the behavior of both algorithms.

Next, we study the broadcast time problem on graphs that comprise some recursive structures. We introduce an exact polynomial-time broadcasting algorithm on closed chains of rings. A closed chain of rings is a sequence of cycles, where every two consecutive cycles, and the first and the last cycles, share a common vertex. Additionally, we initiate a novel direction to designing broadcasting algorithms on recursively defined graphs. We provide a theoretical foundation for future broadcasting studies, as well as discuss several practical applications of the approach we introduce.

Last, we study the problem on k-path graphs, one of the simpler graph families with intersecting cycles, for which both an exact broadcasting algorithm and NP-hardness results remain unknown. To better understand the challenges of broadcasting in arbitrary graphs, families with intersecting cycles are crucial to study. We improve the current best approximation ratio for broadcasting on k-path graphs by a multiplicative factor of two. Further, we propose a new optimization problem called 3-List-Sub and study some restricted instances of this problem. We reduce the broadcast time problem on k-path graphs to 3-List-Sub helping us to design an optimal broadcasting algorithm on restricted k-path graphs which was unsolved to date.