ALGORITHM OF PACKING ITEMS INTO PATH - GRAPH WITH CONSTRAINTS ON ADJACENT NODES

A path - graph is a graph that can be arranged in a linear sequence that two nodes are adjacent if they are consecutive in a sequence, nonadjacent otherwise [1] . In this paper, we will think of the situation that there is a path - graph of ? nodes and a set of ? positive numbers which are less than a constant number ? . Every node in the graph will be packed with a number in the set satisfying following constraints. First, sum of numbers in two adjacent nodes must be less than ? . And first and last node has number limits that will be packed in each nodes. Then we want to check if the set of numbers is feasible to the path - graph or not. We will call the ? positive numbers ‘items’. The classic method of checking all possible cases can be done. But it takes too much computin g time in the worst case. A lgorithm we introduce reduces the complexity from ? ( ? ! ) to ? ( ? 2 ) .