In computing Triconnected components of a graph using HopCropt and Tarjan algorithm, i.e https://sci-hub.tw/https://epubs.siam.org/doi/pdf/10.1137/0202012, they compute two additional values Lowpt1 and Lowpt2, in addition to a dfs number, while computing a DFS tree of a given undirected graph. Let frond or back_edge be the edge which is not part of DFS tree. Additionally, Let each vertex is identified by its dfs number, then :
1. Lowpt1(v)=min({w| there exist back_edge xw, where x is descendant of v} U v}).
2. Lowpt(2)=min({w| there exist a back_edge xw, where x is descendant of v} \set_minus Lowpt1(v)} U v})
Now, for computing these values inside a dfs, the standard procedure given is given below.
However, i want to compute
3. Lowpt(v)=min({w| there exist back_edge xw, where x is a descendant of v})
4. Lowpt2(v) = same as above with lowpt1 replaced by lowpt(v)
. In other words, i want to exclude the parameter v from the Lowpt1(v). I want to know what will be the changes required for computing Lowpt(v) in addition to dfs number and Lowpt2(v).
Thanks in Advance for your help.
' An algorithm is as :[Standard DFS procedure (for computing lowpt1 and lowpt2, insert statements given below as comments in their corresponding flagged position)][1]
PROCEDURE 1.
begin comment routine for depth-first search of a multigraph G represented by
adjacency lists A(v). Variable n denotes the last number assigned to a
vertex;
integer n;
procedure DFS (, u); begin comment vertex u is the father of vertex v in the
spanning tree being constructed. The graph to be searched is
represented by a set of adjacency lists A(v);
n:= NUMBER (v) := n + 1;
LOWPT1 (v):= LOWPT2 (v):= NUMBER (v);
for w A(v) do begin
if NUMBER (w) 0 then begin
comment w is a new vertex;
mark (v, w) as a tree arc;
DFS (w, v);
if LOWPT1 (w)< LOWPT1 (v)then begin
LOWPT2 (v) min (LOWPT (v), LOWPT2 (w))
LOWPT1 (v):= LOWPT1 (w);
end else if LOWPT1 (w) LOWPT1 (v) then
LOWPT2 (v) := min (LOWPT2 (v), LOWPT2 (w)};
else LOWPT2 (v) := min (LOWPT2 (v), LOWPT1 (w)};
end
else if (NUMBER (w) < NUMBER(v)) and ((w 4= u) or -a FLAG(v))
then begin
comment the test is necessary to avoid exploring an edge
in both directions. FLAG (v) becomes false when the
entry in A(v) corresponding to tree arc (u, v) is
examined;
mark (v, w) as a frond;
if NUMBER (w) < LOWPT1 (v)then begin
LOWPT2 (v):= LOWPT1 (v);
LOWPT1 (v):= NUMBER (w);
end else if NUMBER (w) > LOWPT1 (v) then
LOWPT2 (v) := min {LOWPT2 (v), NUMBER (w)};
end;
if w u then FLAG (v) false;
end;
end;
n:=0;
for "= until V do begin
NUMBER (0 := O;
FLAG (0 true;
end;
comment the search starts at vertex s;
DFS (s, 0);
end;
`
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs