Paste: graph theory question
| Author: | slava |
|---|
| Mode: | text |
|---|
| Date: | Mon, 3 Aug 2009 15:49:09 |
|---|
Plain Text |
Suppose I have a graph G = (V,E). There might be multiple edges between two vertices.
Given a set of edges X, I want to find the set of vertices W in V such that for w in W, there is a cycle that starts and ends at w with at least one edge of the cycle contained in X.
| Author: | anonymous |
|---|
| Mode: | text |
|---|
| Date: | Mon, 3 Aug 2009 16:09:08 |
|---|
Plain Text |
it doesn't matter in a cycle if something "starts or ends" it.
If you have another idea of what starts or ends mean, then encode it. Otherwise, don't worry, you just want w to be part of a cycle of the edges in X
| Author: | littledan |
|---|
| Mode: | factor |
|---|
| Date: | Mon, 3 Aug 2009 17:31:56 |
|---|
Plain Text |
1. Calculate the strongly connected components of the graph. This partitions the set of edges
2. Find the components for each member of X
3. Take their union, and get the set of vertices that any of the edges touch
You can get strongly connected components with Tarjan's algorithm:
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Tarjan's algorithm seems to allow partial computation of SCCs: it's easy to just calculate the components which go through X, and not incur cost for the other components.
| Author: | Not sure |
|---|
| Mode: | factor |
|---|
| Date: | Mon, 3 Aug 2009 20:08:27 |
|---|
Plain Text |
Not sure that's right littledan but I don't have a better solution :-)
New Annotation