java - Java での近似最小フィードバック アーク セットの実装

Question

Java での最小フィードバック アーク セットの近似アルゴリズムの実装を見つけたいのですが、これまでのところ何も見つかりませんでした。何か心当たりのある人はいますか？

Answer 1

実装できる最も単純な近似アルゴリズム（ただし、最小性の保証はありません）は、このペーパーの1つであるように見えます。

P. Eades、X。Lin、WF Smythによる、フィードバックアークセット問題の高速で効果的なヒューリスティック。

実装は非常に簡単で、大きなグラフでは非常に高速に動作します（250万のエッジと約10万のノードのグラフで試し、1分以内にすべてのサイクルを中断しました）。