The problem of time separation of events is an important problem in interface timing verification. Propagation delays are specified as a time bound (upper & lower bound) due to manufacturing and environmental changes. Three types of constraints are required in modelling the properties of a circuit viz. max (AND gate), min (OR gate) and linear (imposed constraints). Computing the maximum separations under these constraints is discussed in the talk.
We restrict ourselves to ACYCLIC constraint graphs. It is known that the problem can be solved in polynomail time in the presence of only a single type of constraint. The problem is NP-Complete when both max and min type constraints are present. The complexity of the problem with max and linear constraint is yet unknown (min + linear is dual of max - linear). It is conjectured that it can be solved in polynomial time. We have studied the best known algorithm( by Yen) which is conjectured to run in polynomial time. We are working on some approaches to have a tight bound on the algorithm and to verify the posed conjecture for max-linear constraint problem.