WARush143's blog

Finding "Source" in a Directed Graph
By WARush143, history, 8 years ago, In English

Hi community!

Today I am interested in this problem:

Given a directed graph, define f(v) to be the number of nodes i such you can reach i from v by moving along edges. For which values of v is f(v) maximum?

I can come up with the O(n2) algorithm, but I wonder if there is an O(n) algorithm.

Thanks!

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

»
8 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it
  • Condense SCC's into single nodes to transform the graph into a DAG.
  • Now every node v of the new DAG will have a value cntv associated with it (number of nodes of the original graph it contains).
  • Now, the solution involves counting in the new DAG the number of nodes in each node's subgraph. As ifsmirnov pointed out, my previous solution was incorrect.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Are you sure? You'll count one node several times.

    4 4
1 2
1 3
2 4
3 4
    → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The science does not now any way of solving this problem faster than O(min(nm, nω)), where ω is a matrix multiplication constant (around 2.3). Could you please share your approach?

→ Reply