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$
2
  • 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$ Commented Mar 24, 2014 at 17:18
  • $\begingroup$ Yes!!! Thanks! It is 3-connected graph problem. $\endgroup$
    – sm2
    Commented Mar 25, 2014 at 7:24

2 Answers 2

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$
2
  • $\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
    Commented Mar 24, 2014 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
    Commented Mar 24, 2014 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .