Abstrait

Computing List of Ordered Pairs from Disjoint Closed Interval to compute a most Probable Delay Path:NPHard in polynomial time

Sujit P Nale , S.P Sonavane

Computing most probable delay of a given graph having node(n) and edges (m) is NP-Hard problem. The hardness of the problem doesn�t impact on the restricted version problem. The main idea is to solve the problem with the help of applying some constraint on given NP-Hard problem. Two different cases are considered to solve the given NP-Hard problem. First case considers as if the constraint satisfied with the problem, then it is easy to solve given NP-Hard problem in polynomial time with the help of approximation algorithm. Second case, otherwise the computational complexity of the problem remains non-polynomial. Normally, the network operator needs to find a source to destination path such that the bandwidth of the path is no smaller than the specified bandwidth requirementand delay of the path is no longer than specified the delay bound.To solve the above problem in polynomial time it is necessary to find a pair of tight lower and upper bound which is in the form of disjoint close interval. In this paper, an algorithm is designed to calculate a set of ordered pairs which is a part of implementing polynomial time algorithm to compute the most probable delay between source to destination for a given graph.