高温処理済みコースケスマートフォン用の表示で見る高温処理済みコースケ2018-02-26俺のFPTの理解FPTにおいては幅とパラメータが存在する。高温処理済みコースケの話。オーダーで上限を決めることができる。今回、最大クリーク問題の幅をk-coreとしたが、その幅は彩色数の近似にもできる。1以下の彩色結果が得られるので、それを幅にしてもよい。その場合でも上限は幅をもとに計算することができる。幅はアルゴリズム上設定されたもので、kは判定問題に与えられるパラメータ。これが指数関数しかないのか、多項式のものもあるのかはまだわからない。探索木を多項式時間で検索できればよい。制限はあるなかでの探索なのでもしかすると多項式時間のアルゴリズムがあるかもしれない。指数時間アルゴリズム入門だと100万頂点からサイズ30以下の頂点被覆を求めることが可能ってなってたけど、補グラフの最大クリークのサイズをnから引いたものが頂点被覆なわけだから、幅hに対してk,h-kが小さければ、もっと全然できるはず。英語のWikiPediaの記事でDegeneracyをつかって最大クリーク問題ができるのが書いてあるな。指数時間アルゴリズム入門だとkに対してと書いてあるので、2変数はちがうんだろうなとおもう。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。