Skip to main content

We can compute the subgraph $G$ using two breadth-first searches and a scan through the nodes and edges in time $O(V + E)$.

We perform a breadth-first search from $s$ in $G$ to get the BFS numbering $d_s(v)$ for each node $v$ in $G$. The BFS number denotes the number of edges in the shortest path from $s$ to $v$. We also perform a breadth-first search from $t$ in the transpose of $G$ (that is the graph with an edge $(v,u)$ for each edge $(u,v)$ in $G$) to get the BFS numbering $d_t(v)$ for each node $v$ in $G$.

For each node $v$ in G, the shortest simple path from $s$ to $t$ that goes through $v$ has length $d_s(v) + d_t(v)$.

Now theThe subgraph $G'$ contains the node $v$ from $G$ if and only if $d_s(v) + d_t(v) \leq l$. (We keep the edges from and an edge $G$ that connect two nodes in the subgraph$(u,v)$ if and only if $G'$$d_s(u) + d_t(v) \leq l-1$.)

We can compute the subgraph $G$ using two breadth-first searches and a scan through the nodes and edges in time $O(V + E)$.

We perform a breadth-first search from $s$ in $G$ to get the BFS numbering $d_s(v)$ for each node $v$ in $G$. The BFS number denotes the number of edges in the shortest path from $s$ to $v$. We also perform a breadth-first search from $t$ in the transpose of $G$ (that is the graph with an edge $(v,u)$ for each edge $(u,v)$ in $G$) to get the BFS numbering $d_t(v)$ for each node $v$ in $G$.

For each node $v$ in G, the shortest simple path from $s$ to $t$ that goes through $v$ has length $d_s(v) + d_t(v)$.

Now the subgraph $G'$ contains the node $v$ from $G$ if and only if $d_s(v) + d_t(v) \leq l$. (We keep the edges from $G$ that connect two nodes in the subgraph $G'$.)

We can compute the subgraph $G$ using two breadth-first searches and a scan through the nodes and edges in time $O(V + E)$.

We perform a breadth-first search from $s$ in $G$ to get the BFS numbering $d_s(v)$ for each node $v$ in $G$. The BFS number denotes the number of edges in the shortest path from $s$ to $v$. We also perform a breadth-first search from $t$ in the transpose of $G$ (that is the graph with an edge $(v,u)$ for each edge $(u,v)$ in $G$) to get the BFS numbering $d_t(v)$ for each node $v$ in $G$.

For each node $v$ in G, the shortest simple path from $s$ to $t$ that goes through $v$ has length $d_s(v) + d_t(v)$.

The subgraph $G'$ contains the node $v$ from $G$ if and only if $d_s(v) + d_t(v) \leq l$ and an edge $(u,v)$ if and only if $d_s(u) + d_t(v) \leq l-1$.

Source Link
Mathias Rav
  • 393
  • 2
  • 10

We can compute the subgraph $G$ using two breadth-first searches and a scan through the nodes and edges in time $O(V + E)$.

We perform a breadth-first search from $s$ in $G$ to get the BFS numbering $d_s(v)$ for each node $v$ in $G$. The BFS number denotes the number of edges in the shortest path from $s$ to $v$. We also perform a breadth-first search from $t$ in the transpose of $G$ (that is the graph with an edge $(v,u)$ for each edge $(u,v)$ in $G$) to get the BFS numbering $d_t(v)$ for each node $v$ in $G$.

For each node $v$ in G, the shortest simple path from $s$ to $t$ that goes through $v$ has length $d_s(v) + d_t(v)$.

Now the subgraph $G'$ contains the node $v$ from $G$ if and only if $d_s(v) + d_t(v) \leq l$. (We keep the edges from $G$ that connect two nodes in the subgraph $G'$.)