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?


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.