3
$\begingroup$

Consider the dominator tree of, say, the graph of objects in memory, computed by a memory profiler - one of the most powerful memory leak debugging features, I believe.

The dominator tree tells you "if you manage to make this object unreachable, you'll reduce overall memory consumption by its whole subtree".

Obviously, the next question is "How do I make this object unreachable?", and the dominator tree gives only a partial answer to that: "by disconnecting it from this parent node which dominates over it".

Min-cuts would answer this remaining question ("how do I make this node unreachable from that node"). I already asked a general question about this and unfortunately it stayed unanswered, but I think it would be useful to, at least, produce a dominator tree where every parent-child edge would be annotated with the size of the minimum cut between them.

I'm wondering: is there an algorithm for efficiently computing a dominator tree annotated in this fashion?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.