A Graph Minor Perspective to Network Coding: Connecting Algebraic Coding ... - todo314 @ ウィキ

A Graph Minor Perspective to Network Coding: Connecting Algebraic Coding with Network Topologies

• Xunrui Yin, Yan Wang, Zongpeng Li, Xin Wang, Xiangyang Xue
• INFOCOM 2013

• ぶっちゃけ良く分からない
• Network Coding
  • 例えば、2つのソースが2つの頂点にそれぞれAとBを送信する
  • 辺はAとBの演算結果1つだけしか送信できない
  • A+BとAを受け取ったら、Bを復元できる
  • こんなかんじで上手く情報を伝えたい
  • これの一般化を考えている？
• NC-Minor Conjecture
  • Multicast network GがK_{q+2}をマイナーとして含んでいないとする
  • 有限体F_{f(q)}がGの最適スループットを実現するために十分である
  • f(q): q以上の最小の素数（冪？）
• つまり？
  • 完全グラフがあったらそこを上手く使うと、効率化ができるけど、
  • 無いんだったら、あんまり複雑なことする必要がないってこと？

INFOCOM graph minor network coding

2013-11-22 23:38:41 (Fri)