ダイナミック平面グラフ内の接続されたコンポーネントの数を数える

私は次の問題に取り組んでいます:$ G =(V、E)$を接続された平面グラフにしましょう。私たちの目標は、$ G [V_i]
$が接続されるような$ G $、$ P = {V_1、 ldots、V_d } $の$ d
$パーティションを見つけることです。$ min_ {V_i in P} | V_i | $が最大化される。
(つまり、パーティションのサイズはできるだけ釣り合っています)。これは、プレーングラフ上の平衡接続パーティションの問題であり、NP完全であることが知られています。

私はこの問題を解決するために山登りを使用しようとしています。 $ C [i] = j $が頂点$ i $が$ V_j
$であることを意味する$ C $を$ | V | $ – 長さの配列とする。これは$ V_k = {i in V mid
C [i] = k } $のような$ V $のパーティション$ P_C $を表します。 $ G_C
=(V、E_C)$を対応するグラフ$ bigcup_ {V_i in P_C} G [V_i] $とする。したがって、$ E
setminus E_C $は、$ u $と$ v
$が異なる頂点サブセットにあるようなすべての辺$(u、v)$の集合です。

この場所での(山登り目的のための)「移動」は、以下のように行われる。元のグラフの頂点$ v $の近傍を$ N(v)= {V
mid(w、v) in } $とする。 $(u、v)$を$ E setminus E_C $の端にする。 $ C
[w] = C [v] $の場合、N(v)$のすべての$ w に対して、$ E_C
$から$(w、v)$を取り除く。そうでなければ、$ C [w] = C [u] $ならば$(w、v)$を$ E_C
$に加える。これは、$ v $が$ u $のサブセットにある別のパーティションを引き起こします。

もちろん、これらのパーティションによって誘導されるグラフには、$ d
$以上の接続コンポーネントが含まれている可能性があります。私はグラフの連結成分の数と$ d
$の間の絶対差に比例してこれらを不利にしたい。問題は、これらの接続されたコンポーネントを見つけることは、1ステップ当たり$ O(| V
| + | E |)$時間かかることです。

I did some snooping around in the space of fully dynamic graph
connectivity algorithms. For general graphs, Holm et al. (see
[1]) achieve $O(log^2 n/log log n)$
insert/delete and $O(log n/log log n)$ connectivity queries
(i.e., are $u$ and $v$ connected?) by using Henzinger and King’s
Euler-tour trees (see [2]). For planar graphs, Eppstein et
al. (see [3]) achieve $O(log n)$
insert/delete/connectivity.

問題は、接続クエリを接続コンポーネント数に変換するのが簡単かどうかわからないため、これらの結果を自分の問題に適応させるのは簡単ではないことです。もう一つは、これらの結果がエッジ挿入と削除をサポートしていることですが、挿入や削除が可能なエッジをすべて知っているかどうかを知りたいのですあらかじめ事前計算を実行し、接続されているコンポーネントの数を増やすことが前提です。

私はまた、以下の洞察力を持っています。上記のように$ v $から$ u $の部分集合を移動するとします。元のグラフ$ G_1
$と新しいグラフ$ G_2 $を呼び出します。 $ G_2 $の中の接続されたコンポーネントの数は$ G_1
$の中の接続されたコンポーネントの数から$ N $の$ w $の頂点の数を差し引いたものです。すなわち、$ u $から$ w
$までのすべての経路が$ v $を通過する)、N(v)$および$ C [w] = Cの$ w に対するブリッジの辺の数$(w、
[v] $(すなわち、$ v $の元の部分集合の削除結合を破る$ v $の隣接する辺の数)。

誰もがこの問題の解決策を知っていますか?あるいは誰にでも論文を読むための提案がありますか?

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です