私は、平面3連結グラフのグラフ同型写像のトピックについていくつかの研究をしましたが、異なる制限、理論複雑性、および使用頻度のアルゴリズムが豊富にあり、目立つものを見つけるのは困難ですよう：簡単に理解することが多面体グラフ（平面3連結グラフ）同型写像のアルゴリズムですか？
を実装することができますそれはせずに知ることは難しいですこの問題のためのより古い、より特殊化されたアルゴリズム、またはより新しい、より一般的なアルゴリズムのいずれかで、私が別のアルゴリズムを自分自身で理解するかどうかを理解してください。 可能性のある候補のうち、どれが/ 1であるのがベストフィットですか？
私はWeinbergのアルゴリズムが法案に適合していると思います。
理解しやすい：平坦テストアルゴリズムの副産物として、G及びHのためrotation systemsを計算します。 GとHは3接続されているので、これらの回転システムは、GとHが同形である場合にのみ時計回りと反時計回りに交換するまで同形です。 Gのダーツ（=指示された方向のエッジ）dを選択し、それをHのすべてのダーツeにマッピングしてください（そして、Hの他の向きについても繰り返す）。 Gが接続されているので、Gの回転システムの2つの操作を構成することによって、他のすべてのダーツd 'に到達することができます。対応する操作をeに適用し、同形が存在するかどうかを確認します。
最大明瞭度：平坦性テストとは別に、上記はコードページです。別の人のプレーナリティテストを再利用できますか？たとえばBoostには1つあります。そうでなければ、私はまだ自分の実装はnautyを書き換えるよりも簡単だと思う。
フラットネステストの後、Weinbergのアルゴリズムは基本的に、各ダーツの深さ優先トラバーサルを同期させたものです。実行時間の合計はO（| V | ）で、大きな定数は潜んでいません。
注：HopcroftとTarjan's | V | log | V |アルゴリズムは比較的簡単です。私は今、彼らの記事にアクセスすることはできません。一方、線形時間平面性テストと二次型平面性テストの違いは、いくつかの素晴らしいデータ構造です。したがって、自分でテストを書くなら、二次的な時間で解決するかもしれません。 –
希望は少し良いです。他のサイトのいずれかに移行するようにフラグを立てることを検討することもできます。私はこれがここで多くの牽引力を得るだろうと確信していません。 – Will
私は懸念を感謝します。私の質問を投稿する前に、これは最高のSEではないかもしれませんが、より適切なSEを考え出すことはできませんでした。理論的な計算機科学ではないようです。ソフトウェア開発に関する概念的な質問ではありません。本当に数学、等...どのサイトでこれが最もうまくいくと思いますか？ –
あなたの推測は私のものと同じくらい良いです。私は主に大手3社（そしてプログラマー）だけに精通しています。 – Will