Блог пользователя tehqin

Algorithms Live! Episode 16 — Ski Resort
Автор tehqin, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 ?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Yes! :)

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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. :)

        → Ответить