A Steiner Problem in Petersen Graph Which is NP - Complete

Dr. G. Nirmala, C. Sujatha

Abstract: In this paper, we will discuss complexity theory, a specific problem known as R-Restricted steiner problem in petersen graph is Np-complete and also every full component of a steiner tree contains almost 4 terminals.

Keywords: steiner minimum tree,NP-complete,satisfiablity,petersen graph