tehqin's blog

Algorithms Live! Episode 16 — Ski Resort
By tehqin, history, 8 years ago, In English

http://algorithms-live.blogspot.com/2017/04/episode-16-ski-resort.html

  • Vote: I like it
  • +54
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hello, firstly thanks for the awesome episode.

I had a query. Can you tell me if the following is correct which I've understood from this episode ?

Dominator tree can be constructed using LCA. To do that, we first topologically sort the nodes in the DAG. Then we process them sequentially. While processing a node, we find out the LCA of the set of nodes who have a direct edge to the current node. Then we can safely say that this LCA is the immediate dominator of the current node. So we simply add the current node as a child of the LCA we've found in the dominator tree and add the sparse table row for the current node in O(logn). Thus we can construct the whole tree.

I think the time complexity would be O(ElogV) as we are finding out LCA once for every edge.

Are the idea I described above and the time complexity analysis correct ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes! :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks. Also is there any other way to build a dominator tree which is more efficient ? I've seen that some people use another method involving DSU but it seemed pretty complicated at first glance.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes. That algorithm works even for graphs with cycles. It is close to linear in runtime. The LCA method only works for DAGs but is much simpler conceptually. It's only a bit slower but the binary lifting table on the dominator tree is sometimes useful for solving other subproblems.

        I will do a future episode on the more power algorithm if there is interest. :)

        → Reply