Minimum Spanning Trees in Temporal Graphs - todo314 @ ウィキ

Minimum Spanning Trees in Temporal Graphs

• Silu Huang, Ada Wai-Chee Fu, Ruifeng Liu
• SIGMDO 2015

概要

• Temporal グラフでのMST
  • 根と時間区間が入力
• MSTa: 線形時間，簡単
• MSTw: 近似，難しい

問題定義

• (u,v)間の辺<s,t>[w]: sに出発tに到着wが重み
• 根r，時間幅[α,β]
• [α,β]の間にrから矛盾が無い全域木が欲しい
  • パスの意味での矛盾をいっている
• MSTa: rからの到着時間を最小化
• MStw: 辺の費用の総和を最小化

MSTaの線形時間アルゴリズム

0時間遷移が無

• 開始時間の早い順に整列して
• 到着時間を更新してく
• 0時間遷移があるとメンドイ
• A-B-C
  • A->Bが<1,1>，B->Cが<1,1>でB->C先だとめんどい

0時間遷移が有

• ちょっと頑張る

MSTw

• NP-hard，MAX-SNP hard
• 最小有向Steiner木 (DST)
  • 終端集合Xを終端とする根rの費用最小木を求める問題
• MSTwから上に変換する
  • 到達時刻の分頂点を複製する
• DSTの近似アルゴリズム[SODA'98]
  • 推移閉包を作る…省略
• DSTの解から簡単にMSTwに戻せる
• MSTwでi^2(i-1)k^1/i近似，O(|E|^i k^{2i})時間