minimario's blog

n log n SSSP in Permutation Graphs
By minimario, history, 7 years ago, In English

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

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

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it
  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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

          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.

          → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply