典型タグ

静的graph等式制約のpotential伝播

可逆な加法・XOR演算で x_v=x_u⊙w と書ける辺等式をDFS/BFSで伝播し、cycle整合性を検査して各連結成分の解をroot offset一つで表す。

この典型を扱う単元: 静的graph等式制約のpotential伝播

検索別名: XOR potential graph、graph potential propagation、グラフpotential、静的差分等式制約

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

扱う対象
  • root-relative potential
  • 加法群またはXOR群
  • 辺等式制約
使う手掛かり
  • x_v=x_u⊙w
  • 全制約が静的
  • 成分ごとの自由offset
保つ不変量
  • component-wide offset
  • cycle consistency
  • path potential
求めるもの
  • 可解性判定
  • 成分offsetの最適化
  • 相対値復元
適用しない条件
  • negative cycle
  • online union/query
  • 不等式の上界
分類・前提・学習成果

分類と直接の前提

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

関連する典型

  • potential・weighted DSU: 固定graph上で等式を一括伝播する方法と、辺追加に追随して差分potentialを保つ方法を区別する。

学習成果と学習単位

代表問題

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

関連問題

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