Daily Arxiv

世界中で発行される人工知能関連の論文をまとめるページです。
このページはGoogle Geminiを活用して要約し、非営利で運営しています。
論文の著作権は著者および関連機関にあり、共有する際は出典を明記してください。

A Customized SAT-based Solver for Graph Coloring

Created by
  • Haebom

作者

Timo Brand, Daniel Faber, Stephan Held, Petra Mutzel

概要

Zykovツリーを模倣したエンコーディングに基づいてグラフの着色問題を解決する新しいSATベースのアルゴリズムであるZykovColorを紹介します。 H ebrardとKatsirelos（2020）のアプローチに基づいており、推移制約を適用し、ナビゲーションツリーを剪定するための下限を統合し、推論された伝播を可能にする伝播者を使用します。 CaDiCaLのために最近導入されたIPASIR-UPインターフェースを活用して、SATソルバーでこれらの技術を実装します。また、頂点支配ヒントを使用した統合決定戦略の変更や、以前の呼び出しで学習された句を再利用するための段階的なトップダウン検索など、SATソルバーを活用する新機能を提案します。さらに、検索中の剪定に使用される下限を改善するために、より効果的なクリック計算と分数彩色数を計算するアルゴリズムを統合します。 DIMACSベンチマークセットでは、他の最先端のグラフ着色実装よりもZykovColorが優れていることがわかります。さらに、ランダムなErd\H{o}sR enyiグラフのさらなる実験は、非常に希少または非常に密集したグラフの両方で最先端のSATベースの方法を上回るか、一致することを示しています。 Erd\H{o}sR enyi グラフで他の SAT ベースの方法を上回る ZykovColor の追加構成を提供します。

Takeaways、Limitations

•
Takeaways：
◦
ZykovColorは、グラフの着色問題を解決する新しいSATベースのアルゴリズムです。
◦
最先端のグラフの着色実装よりもパフォーマンスが優れています。
◦
非常に稀であるか非常に密なグラフの両方で、最先端のSATベースの方法と同等または優れた性能を示します。
◦
頂点の支配的なヒント、徐々にトップダウン検索、効果的なクリック数の計算、分数色の数の計算などの新機能が統合されました。
•
Limitations:
◦
論文ではLimitationsへの明示的な言及はありません。
👍
Made with Slashpage