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$
4
  • $\begingroup$ So the input is a starting node and the output is the maximum node reachable? $\endgroup$
    – cr001
    Commented Nov 10, 2015 at 8:49
  • $\begingroup$ Yes. But we need to find the maximum node for all the nodes in the graph. $\endgroup$
    – rameesh
    Commented Nov 10, 2015 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
    Commented Nov 10, 2015 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
    Commented Nov 10, 2015 at 13:17

1 Answer 1

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$
2
  • $\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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 at 22:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .