Graph value propagation algorithm -

i've got directed graph (n, a), each node n[i] has value v[i] , threshold t[i]. each arrow (n[i], n[j]), invariant v[i] <= v[j] holds. need efficiently implement following operations:

• increasethreshold(i, x): set t[i] = max(t[i], x). that's trivial , completeness here.
• increasevalue(i, x): set v[i] = max(v[i], x) , increase other values needed above invariant holds.
• evaluate(i): return true if v[i] < t[i]

the straightforward implementation store v[i], t[i], , outgoing arrows each node. on increasevalue(i, x), it'd propagate value along outgoing arrows (using set of "open" nodes many other graph algorithms do). v[i] stored each node, evaluate(i) trivial.

as increasevalue more frequent other operations, eager approach seems wasteful. wonder, if lazy propagation v[i] recomputed needed more efficient. this, i'd maintain w[i] maximum of x increasevalue(i, x) , compute v[j] on fly when evaluate(j) needs it. can computed maximum of w[i] on nodes n[i] there's path n[j]. actually, once know v[j] >= t[j], exact value v[j] doesn't matter , can stop computation.

unfortunately, lazy algorithm inefficient, doesn't pay off increasevalue being orders of magnitude more frequent evaluate.

i imagine, "partially lazy" algorithm better, that's intuition , can't make progress it.

is somehow well-known problem? other idea?