I know this forum is not about algorithm but please can you help?

Mar 28 2005 1:35 AM
Hi there. Please I need some help with the following problem which has given me headaches. Here it is: For a connected graph G the following algorithm is executed: -a queue Q is initialized with a graph G -while Q isn't empty -extract the first graph in Q and put it in H -determine A - a minimal articulation set in graph H -assuming that V1,... , Vk are the sets of vertices of the connected components in which H is broken by A, add to Q the following graphs: [A U Vi]H, i =1, n The questions is to prove that the total number of graphs inserted in Q isn't greater that |G|*|G| My note: What does |G|*|G| mean? I was told that it means the number of vertices of graph G squared . Others told me that |G| might mean |V|*|E|. Which is which ? Please can you help? Thanks in advance and please forgive me for the inconvience of posting an algorithm thread in a forum about C# ! Cheers, Adisor

Answers (3)