OK, the problem is, given a strongly connected (directed) graph, find a strongly connected spanning subgraph (SCSS) with the minimum size (i.e., the number of edges). This problem is NP-hard (can be seen by induction from the Hamilton Cycle). No efficient algorithm is known to compute a minimum solution exactly.

In paper "A nearly linear time 5/3-approximation of the minimum strongly connected spanning subgraph", we have found an almost linear time algorithm that can find an SCSS with edges at most 5/3 times of the minimum (it is linear time in real life!). I decided to implement the algorithm, which is Project findSCSS. Here comes an implement of JAVA applet (application), which took me three weeks to release the first version (0.1). And after a two-days work, I proudly improved it to version 0.2.

New 2002/09/12. The algorithm can be further improved to run in linear time. Due to the overhead of implementation, however, we still use the old one.



  1. Faster implement. Now I use variable array to hold the graph, which is convenient but slower than a static array.
  2. Load/Save function, etc.

Try it

Try it and please report any problem or suggestion to me. The souce code is also available, contact me too.

version 0.4

This is the inline version (i.e., the applet will appear in the browser area. If you want a more flexible one, use version 0.5 please.

version 0.5

Begin from version 0.5, the calculation frame is a pop-up windows. Thus you can get the most flexibility since you can resize it (which is impossible for an inline version such as version 0.4).

what't new