2
$\begingroup$

There is a Graph G(V,E). All nodes and edges are numbered. Two edges can have same number but all nodes have a unique number.

A path $ v_1, v_2,v_3,...,v_k $ exists if and only if the edge connecting the nodes in the path is in increasing order. I am interested in finding the maximum valued reachable node for each node in the graph.

I have thought of doing Depth First Traversal starting from the highest valued node and marking all those that can visit this node, and so on. But using this approach, we must visit a node more than once.

$\endgroup$
  • $\begingroup$ So the input is a starting node and the output is the maximum node reachable? $\endgroup$ – cr001 Nov 10 '15 at 8:49
  • $\begingroup$ Yes. But we need to find the maximum node for all the nodes in the graph. $\endgroup$ – rameesh Nov 10 '15 at 9:10
  • $\begingroup$ So you want to build this mapping $M:V\rightarrow V$ of the maximum reachable node for each node in linear time? Or strictly every single node cannot be visited twice? $\endgroup$ – cr001 Nov 10 '15 at 9:47
  • $\begingroup$ One node can be visited any number of times. Maximum node for each node should be found (complexity: better if strictly less than quadratic) $\endgroup$ – rameesh Nov 10 '15 at 13:17
0
$\begingroup$

I think you can do it in $|E|\log |E|$.

Sketch:

For simplicity, let's first assume that the labels of the edges are unique. In such case, start with an array $M : V \to V$ initialized with the labels of $V$. Then sort all the edges descending by their labels and for each edge $(u,v)$ set $$M[v] = M[u] = \max\{M[v],M[u]\}.$$ The invariant is that $M[v]$ contains the highest node-label reachable from $v$ via edges with labels at least $\mathtt{label}[(u,v)]$.

When the edge-labels aren't unique, the matter complicates a bit, because there might be a chain of edges having the same label. If the edge-labels on paths should be non-decreasing (weakly increasing), then a careful resorting of current edge-label level by $\max\{M[v_1], M[v_2]\}$ seems like enough (e.g., visiting the changed nodes first is equivalent to a DFS using edges with the same edge-label). For strictly increasing labels on paths use two passes: first gather updates, second apply them.

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ Thanks for your answer :) I have a small confusion, Can you please explain the "careful resorting" part when the edge-labels aren't unique and the path can be weakly increasing. $\endgroup$ – rameesh Nov 12 '15 at 14:05
  • $\begingroup$ You tagged this 'recreational math', so I won't give away all the details. I've already posted too much! $\endgroup$ – dtldarek Nov 12 '15 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.