ei1333の日記

ぺこい

う　し　た　ぷ　に　き　あ　く　ん　笑って何？元ネタは？調べてみました！

皆さんこんにちは！

近頃、ツイッターのTLでよく見る言葉、う　し　た　ぷ　に　き　あ　く　ん　笑

意味や元ネタを知らずに使っている人も多いのでは？

せっかくなので、う　し　た　ぷ　に　き　あ　く　ん　笑について自分なりに調べてみました！

続きを読む

木幅が2以下のグラフの木分解と動的計画法

なんだこのよくわからんたいとる

卒論を書いているだけだと精神衛生上よくないので, つらくなったときに書いていました.

木幅・木分解についてと, 木分解上で動的計画法をするアルゴリズムについて解説します.

例えば最大独立集合は木幅 {t} として {O(2^{t+1} t^2 V)} とかで解けます.

また, 一般に木分解を求めるのはヒューリスティックなどをする必要があり最悪ケースを考慮する競プロ的には難しい(難しくなかったら教えてください)ので一般グラフに対する木分解はどこかの記事や本などを読んで頂くこととして, ここでは有用そうな木幅が {2} 以下のグラフの木分解について解説します. ちなみに木幅が {2} 以下のグラフは カクタス, なもりグラフ, 外平面グラフなどのSeries-parallel graph(直並列グラフ) などを含みます. カクタスみたいなのはこどふぉでよくみるかも.

続きを読む