n個の頂点のグループごとのグラフ分割

Question

最大n個の頂点のグループでグラフを分割できるグラフ分割方法はありますか？

例：私は1000個の頂点を持つグラフを持っており、最大100個の頂点を持つサブグラフで分割したいと思います。アルゴリズムがこれをより良く見いだせば、それぞれ50個の頂点を持つ2つの部分グラフが存在する可能性があります。

私はk-meansを使ってメソッドを見つけました.k-の後には、各クラスターに100個の頂点を持つようにクラスターを「較正」することを意味しますが、このメソッドは時間がかかると思います。

アイデア？

編集：OK、サブグラフを求めるのは間違いかもしれません。ちょうどkmeansがどのように働いているのか想像してみましょう。グラフを小さなグループに分割したいのですが、各グループのTSP問題を解決した後、すべてのグループを最も近いグループにリンクし、グループの中心に3optの移動を適用します。しかし、これを行うには、最大n個の頂点を持つグループを見つけるためのパーティションメソッドが必要です。アルゴリズムは、n個の頂点を有するk個のグループを見つけることができ、いくつかの頂点がない場合には、残ったものと別のグループを作る。頂点はランダムに選択されておらず互いに接近していなければなりません。

Answer 1

これについて調査する必要があります。私はあなたの目的に役立つKernighan-Linと呼ばれる発見的アルゴリズムを覚えています。残念なことに、あなたはそれを一般化する必要があり、時間は本当に悪いです。私はそれがO（N^3）の周りにあると信じています。

さらに専門的ですが複雑なアプローチは、スペクトルパーティショニングを使用することです。ダイレクトサイエンスウェブサイトで使用できるこのトピックに関する非常に詳細な記事があります。以下はこのトピックへのリンクです：Spectral partitioning works: Planar graphs and finite element meshes。

私はこれがあなたの探求に役立つことを願っています。しかし、私はこれが簡単なことではないことを警告しています。がんばろう！