WARush143's blog

Finding "Source" in a Directed Graph
By WARush143, history, 9 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

»
9 years ago, hide # |
← 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
»
9 years ago, hide # |
 
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