The client has made the following changes to the job.
Client prefers freelancers from:
You are still able to submit a proposal for this job.
The client prefers freelancers from
a different location.
We are using the boost graph library for a project where computing the graph connectivity is a key step. There exists a function connected_components, as well as incremental_connected_components, which are useful. However, we are going to be both adding and deleting edges, so neither of these algorithms is appropriate. There is some recent work by Holm, J., de Lichtenberg, K., and Thorup, M., entitled Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and bi-connectivity (attached as a PDF). This work contains an algorithm to solve this problem. We'd like an implementation of this algorithm, in the style of the boost graph library, with interface based on the incremental_connected_components. There are some possibilities for extending this work as well, dependent on the results of the initial implementation.
- You must have either a B.S. or M.S. in Computer Science or Mathematics
- Need to understa...
Sign in or Register to see more