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

n log n SSSP in Permutation Graphs
Автор minimario, история, 7 лет назад, По-английски

Hi all,

Apparantly there is way to find SSSP from a single point, but I have tried a while and could not come with it. Can anyone help?

There is article here, but I have to buy it for USD$31.50.

So anyone can tell me about the algorithm for free?

Thanks,

-minimario

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
  1. Insert a starting vertex in queue, and remove it on graph
  2. while que is nonempty, pop one, and insert all adjacent vertex, and remove them all in graph

We need data structure to find "one" adjacent vertex, and remove that vertex. Use max segtree.

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

    Oh, thank you very much, I see now. I overlooked something so simple :)

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

      Algorithm itself is easy, but I'm not sure coming up with this is also easy :p

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Sorry, ignore it! But I can't delete it :)

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

          It's okay :)

          Not sure about that linear one, but I think it's quite easy to handle weighted version with this algorithm.

          1. Insert a starting vertex in priority queue with vertex weight, and remove it on graph
          2. While pque is nonempty, pop one, and insert all adjacent vertex (with their vertex weight added), and remove them all in graph

          Note that relaxation is necessary for only one time. It's due to the fact the weight is in vertex, not edge.

          → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

Btw you can use sci-hub.io to get the paper for free.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BTW, are there any interesting problems that use some properties of this graph?

→ Ответить