Author |
Topic: Breaking a Strongly Connected Graph (Read 895 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Breaking a Strongly Connected Graph
« on: Nov 22nd, 2004, 5:21am » |
 Quote  Modify
|
It seems this time I need a help from the forum members… (but that's not a homework  )
Assume I have a Strongly Connected Graph (SCG) with n nodes. I want to break it into some number of smaller strongly connected components (SCC) by choosing a node and deleting all its connections.
Now, I define the “quality” of breaking to be the minimum of max |SCC|, that is the minimum of the maximal number of nodes in remaining SCCs. According to this, breaking the SCG into 2 SCCs with [approx]n/2 nodes is better than breaking it into 2 SCCs with n-3 and 2 nodes.
The question is: Propose an efficient algorithm to choose a good candidate for breaking. “Efficient” in this case means that O(n2) will not do.
Is this question considered in the literature?
|
| « Last Edit: Nov 23rd, 2004, 1:45am by Barukh » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Breaking a Strongly Connected Graph
« Reply #1 on: Nov 22nd, 2004, 11:30am » |
Quote Modify
|
on Nov 22nd, 2004, 5:21am, Barukh wrote:It seems this time I need a help from the forum members… (but that's not a homework )
|
|
Quote:
Now, I define the “quality” of breaking to be max |SCC|, that is maximal number of nodes in remaining SCCs. According to this, breaking the SCG into 2 SCCs with [approx]n/2 nodes is better than breaking it into 2 SCCs with n-3 and 2 nodes.
|
|
Isn't max |SCC|= n-3 better than n/2 ?
Are you trying to maximize the minimum?
i.e maximize Q = min {|SCCi|}
|
| « Last Edit: Nov 22nd, 2004, 11:31am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Breaking a Strongly Connected Graph
« Reply #2 on: Nov 23rd, 2004, 1:44am » |
Quote Modify
|
on Nov 22nd, 2004, 11:30am, Aryabhatta wrote:
Are you trying to maximize the minimum?
i.e maximize Q = min {|SCCi|}
|
|
Sorry, I don't know what I was posting... I am trying to minimize the maximum, that is:
minimize Q = max {|SCCi|}.
|
|
IP Logged |
|
|
|
Miles Teg
Newbie
Gender:
Posts: 11
|
|
Re: Breaking a Strongly Connected Graph
« Reply #3 on: Nov 23rd, 2004, 9:39am » |
Quote Modify
|
Just a note (not a solution  ):
If we have n nodes then at the WC is O( n[smiley=sup2.gif]) edges .
The best algorithm for finding SCG (lets say Kosaraju Sharir ) has runtime [smiley=comega.gif] (v +u) where v- number of nodes and u number of edges .
Therefore just to find the SCG we need O(n [smiley=sup2.gif]).
Maybe this should be refined to be O(v+u) or O((v+u)(logu + log v)) .
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print