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

Finding "Source" in a Directed Graph
Автор WARush143, история, 8 лет назад, По-английски

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!

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

»
8 лет назад, # |
← Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится
  • 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.
→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

→ Ответить