0
$\begingroup$

I need to find partition (S) (with more then 2 nodes) of a non-oriented graph (G), that containes no more than two nodes connected with the rest of graph (G \ S)

I could invent an algorithm of brute force of pairs of nodes, but I need a more optimal algorithm.

$\endgroup$
  • 1
    $\begingroup$ I think you need to clarify your problem a bit more in order for anyone to be able to answer it. A partition of a graph is usually a partition $S = (V_1, V_2, \dots V_k)$ of the vertices of the graph. What does $G \backslash S$ mean? Are you saying $S$ is a set of nodes of the graph so that $|\{v \in S : uv \in E(G) \textrm{ for some } u \in V(G)\backslash S\}| \leq 2$? In which case, are you really just asking to find a 0-, 1-, or 2-separation of the graph? $\endgroup$ – Perry Elliott-Iverson Mar 24 '14 at 17:18
  • $\begingroup$ Yes!!! Thanks! It is 3-connected graph problem. $\endgroup$ – sm2 Mar 25 '14 at 7:24
1
$\begingroup$

Assuming you're looking for 2-separations in a 2-connected graph, the following paper of Hopcroft and Tarjan could be useful. They find the triconnected components of a graph in $O(v+e)$ time:

http://ecommons.cornell.edu/bitstream/1813/6037/1/74-197.pdf

See also: http://en.wikipedia.org/wiki/SPQR_tree

$\endgroup$
0
$\begingroup$

This problem is NP-Hard. So the best you'll get are approximations or inefficient algorithms.

A couple algorithms are: Kernighan-Lin: http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm

Fiduccia-Mattheyses: http://en.wikipedia.org/wiki/Fiduccia-Mattheyses_algorithm

$\endgroup$
  • $\begingroup$ Your algorithms solves bipartition problem with goal to balance nodes's weight, but I have another problem - key statement is only two nodes in partition may have connections with nodes outside partition $\endgroup$ – sm2 Mar 24 '14 at 13:35
  • $\begingroup$ I found this link (sandia.gov/~bahendr/partitioning.html) on a quick Google search. It seems a fair amount of research has been done on the subject. I'd probably start with these research papers. $\endgroup$ – ml0105 Mar 24 '14 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.