Skip to content

r-gg/fb_arc_set

Repository files navigation

Minimal Feedback Arc Set

The algorithm removes cycles in a directed graph by removing the least edges possible. A set of edges that must be removed to make a graph acyclic is also called a feedback arc set; and the set with the least edges is a minimal feedback arc set.

Implementation

There are two programs: a generator program and a supervisor program.

Multiple generator processes generate random solutions to the problem and report their solutions to one supervisor process. The supervisor process remembers the best solution so far. The processes communicate with each other by means of a circular buffer, which is implemented using shared semaphores and a shared memory.

Example

image

Invocation

image

About

Parallelized solution to the Minimal Feedback Arc Set problem.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Contributors