Extending the Limits of Tractability and Intractability for Steiner Tree Domination and its Variants on Structured Graphs

Abstract

One of the important aspects of algorithmic graph theory research is to identify the boundaries of tractability and intractability for computationally difficult problems. The objective of this thesis is to analyze the computational complexity of several problems related to the Steiner tree problem and the dominating set problem, in particular, a thin line separating P vs. NPC instances of the Steiner tree and Domination problems, and its variants. newline