## Introduction

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.

## Feature

- Platform independent: it is written in JAVA. You only need a browser with JAVA2 support.
- Simple: draw a graph and get the SCSS. I tried to make the program as simple as possible.
- Fast: I have tested (drawn) a graph with 51 nodes and 150 edges, and it returns in less than 1 second (see screenshots draw graph, find SCSS).
- Other: you can repeatedly replace the graph by the computed SCSS and compute again. This often yields better solutions.

## ToDo

- Faster implement. Now I use variable array to hold the graph, which is convenient but slower than a static array.
- 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

- 2003/01/24, version 0.5: now a pop-up windows is used to increase flexibility.
- 2002/09/12, version 0.4: better drawing method. Now there is no flicker when drawing. SWING is great.
- 2002/07/22, version 0.3: when the graph is not strongly connected, the program can now give the user an advice for adding an edge. There are also some bug-fixes which may give wrong result if the start node of DFS is not 0.