典型タグ

path matchingのheap縮約greedy

pathの非隣接edgeからk本を選ぶ最小重みmatchingを、最小edgeの採用と近傍二辺の補正縮約 w_l+w_r-w_i により全cardinalityについて順に求める。

この典型を扱う単元: path matchingのheap縮約greedy

検索別名: minimum k-matching on a path、path matching contraction、path matching縮約

未知問からこの典型を見つける手掛かり

扱う対象
  • linked alive edges
  • nonadjacent selection
  • weighted path edges
使う手掛かり
  • pathから隣接しないk辺
  • 全kの最小費用
  • 最小辺を選んで近傍を縮約
保つ不変量
  • selected prefix is optimal by cardinality
  • 補正edge preserves every remaining optimum
求めるもの
  • cardinality別最小matching費用
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

学習成果と学習単位

  • 重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。

    path matchingのheap縮約greedyで学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。