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

Автор comtalyst, 7 лет назад, По-английски

Problem statement : Given a degree sequence D. Can we create a simple graph (graph without self loops and parallel edges) from D?

This is a classical problem that can be solved by using Havel-Hakimi algorithm or Erdős–Gallai theorem. Both of them have time complexity O(n^2). But I have found a task with N <= 100000 which is incompatible with O(n^2) algorithms. Is there any faster method to solve this?

(Edited) There are no any special conditions in this task

(Edited) Solved!! Optimize Erdős-Gallai Algorithm by using binary search to find min(di,k) of each k efficiently. New time complexity is O(n log n). Thanks 300iq and animeshf for this idea!

Link for Erdős-Gallai algorithm : https://en.wikipedia.org/wiki/Erdős–Gallai_theorem

Thanks everyone for replying.

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

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

Gale-Ryser may work if your graph is bipartite.

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

Havel Hakimi can be implemented in such a way so that the complexity becomes O(Summation of degrees of all nodes * log(n)) which can be smaller than O(n^2) depending on the input constraint. What is the constraint on the degrees of the nodes in your problem?

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

    Sadly, It seems there is no special condition about this too.... ;( All degrees can be at most N.

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

      I guess you have to output the edges, so sum(degrees) can't be too large, because you have to print out 2*sum(degrees)/2 numbers, which would be impossible for numbers like > 10^7.

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

Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).

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

Seems like some people wrote a paper on optimizing Erdős-Gallai from O(n2) to O(nlogn) (or O(n) if D is already sorted). The relevant part is the 15 line pseudocode on page 6 (It is pretty self-explanatory).

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

Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).

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

    Can you share the problem link?

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

      This problem come from a thai competitive programming site named CodeCube. Here is the problem link.

      Unfortunately, official problem description and the whole site is in Thai only (but it isnt hard to be analyzed). And you will have to register before submit.

      Here is my brief English translation: Given Q — number of queries (Q <= 10). Each query contains N — number of vertices in the graph (N <= 100000) followed by a degree sequence, each of them doesnt exceed N. For each query, answer "Yes" or "No".