ABSTRACT
This chapter begins with a general description of computational complexity analysis of a problem, and shows us the approach on how to prove polynomial time (NP)-completeness of a problem. It discusses the proof of NP-completeness of some problems related to elastic optical networks. The space complexity of an algorithm indicates the amount of space taken by the algorithm to run as a function of its input size. The chapter presents the proof of NP-completeness of some well known problems. It deals with the graph coloring problem and then move to some problems related to optical networks. In the 3-coloring problem, assign each node of a graph with one of three different colors under the condition that a pair of adjacent nodes connected by an edge does not use the same color. The establishment of lightpath using static traffic assumption is known as static lightpath establishment problem.
