グラフの密度

k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。超訳 Abstract最新のグラフマイニングツールでは、k-core分析によりグラフを階層構造に分解するのは標準的な操作です。k-core分解は…

Git LFSは別にリポジトリサーバー側で対応が必要なわけではなくて、LFSサーバーが必要なだけ

GitHubやbitbucketのLFS対応もなんかストレージの料金がすごい高いなぁとおもっていて、リポジトリをホストするサーバーで対応が必要とおもっていたのですが、調べてみるとどうやら違うようでした。ydkk.hateblo.jpLFSサーバーをAWS Lambdaに構築して、S3を…

TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。 https://nekop.hatenablog.com/entry/20131220/1387524669 EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で…

俺のFPTの理解

FPTにおいては幅とパラメータが存在する。たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。 k-クリーク判定では幅に対しての組み合わせになるので二項定理からなので、を用いてのオーダーで上限を決め…

なんとなく

最大クリーク問題のの中身を分解して、の多項式になっていることを証明しないとダメな気がしてきた。わかった。ZPP=EXPTIMEでP≠NPのほうだ

最大クリーク問題つづき

グラフのDegeneracyをkとすると前処理後、おおまかで最大クリークが求まるな。Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフを順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。最大出次数をとする…

K4の対辺をつなぐ話(2)

前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、 kousuke.hatenablog.comそれって式にするとこういうことになるのかな? fはの辺を頂点にして、がの時に辺とするような変換。 完全グラフについては証明できそうだけど…

保育士は「誰でもできる仕事」か?について

news.yahoo.co.jpでこの記事に対して、下記のようなブクマコメントをしたのだけれど、1つではあるけれど、スターがついてしまったのでメモ代わりに書いておこうとおもう。保育士は「誰でもできる仕事」か(駒崎弘樹) - 個人 - Yahoo!ニュースホリエモンは保育…

選挙とか

興味はもつのだけれども、投票したい政党とかがないなぁ。 二大政党制とか目指すのやめたほうがいいんじゃないの?とおもってきた。 STOP安倍政権のスローガンとかみていると、そもそも単独政党による過半数とかできるルールが悪いんじゃないかとおもってきた…

K4の対辺を繋ぐグラフにしてみる

の各辺を頂点にして、その完全マッチングの対に辺を引くという変換をおもいついて、やってみたら面白かった。 → 1頂点 → 3頂点、辺無し → 6頂点、3本の辺 → petersenグラフ → 正則グラフ → 正則グラフ Rの右肩が次数、右膝が頂点数。たぶんあってるとおもう…

計画性

自分はすごく計画性がないなとおもっているんだけど、最近すこしづつ計画性がついてきたとおもっていて、それでも人から期待される程度の1割以下だとおもっているので、自分の成長を自分でほめて、且つ、人には申し訳ない感じなので、大変こころがつらい。

ヒューリスティックな彩色

k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続…

最大出次数を最小にする順序/Rubyのpriority queue

kousuke.hatenablog.com以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。Degeneracy (graph theory) - Wikipediaアルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。…

最大クリーク問題(改)

最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。補グラフをk彩色できたら、…

P≠NP予想が嫌い

P≠NP予想 - Wikipedia 多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。 別にP=NPでもP≠NPでもどっ…

続(4) - 最大クリーク問題

多分4じゃないかと思う。ナンバリングは適当 グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ 補グラフが非連結も同様 すげぇコンパクトになるんですけどって感じだ。これが…

巡回セールスマン問題

最大クリーク問題は改善があって、これでいいってところまで来たので一旦終わり。 巡回セールスマン問題でなんとなくアイデアが湧いて、葉指定 + k-best最小全域木問題に帰着できないかな?とおもっている。 ハミルトン閉路から一本辺取り除いたら道だけど、…

最大クリーク問題の現在

Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースでがはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあっ…

最大クリーク問題で面白いなとおもったこと

いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。 ある無向グラフGについてを最大クリークサイズを返す関数とする。f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフをとすると g(m) : グラフが非…

補グラフでの最小頂点被覆ってなんだろう?

補グラフでの最小頂点被覆ってなんだろう?って考えてて、最大クリークの頂点以外の頂点集合って意味しかないのかな

最大クリークの途中で補グラフが出てくる話

kousuke.hatenablog.com 前回、ワーストケースでになると書いた。FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか? 簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。最大クリーク判定の式を…

最大クリークの計算量とか(続き)

kousuke.hatenablog.com 大事なことに気が付いたので、前回の修正。単純な無向グラフに対し、をサイズkのクリークが含まれるかどうかを判定する関数とする。グラフGに自身を除く全頂点に接続する頂点がある場合、それらは必ず最大クリークに含まれる。そのよ…

グラフと補グラフの関係

kousuke.hatenablog.comn頂点の完全グラフを、独立グラフ(頂点のみで辺がないグラフ)をとする。n頂点のグラフがある。 このときからへひとつづつ辺を消していく順序集合のうち、を含む順序の集合を定めることができる。このときのどの順序を通ってもの補グラ…

P=NPだと夢がある。

kousuke.hatenablog.com 頂点に関しては極大グラフが1つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。 これは一緒に補グラフの最大独…

最大クリークの計算量とか

修正しました。 kousuke.hatenablog.com (以下、古い内容)をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)最大サイズkのクリークを含む、単純な無向グラフがあるとする。頂点vに隣接している頂点の集合をとし、に対…

続々々 最大クリーク問題(2)

すこしコードを変更している。興味ある人はpaiza.ioで動かしてみてほしい。 https://paiza.io/projects/14TYw6RR2KIPBLRjSNCPrgV=1000、E=9988、20彩色可能、最大次数 69、次数の分布具合は下記のグラフを参考。 最大クリークは8。列挙しているわけではない…

続々々 最大クリーク問題

基本的には前書いた内容。 kousuke.hatenablog.com1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。 動作 0. 頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で…

UnionFind木(簡易版/ruby)

すこし忘れていたのでメモ rootで親をつなぎかえるのが肝。 class UnionFind < Array def initialize(n) super(n){|i| i} end def root(i) self[i] == i ? i : self[i] = root(self[i]) end def unite(i,j) self[root(i)] = root(j) end def same?(i,j) root…

ハドワイガー予想って

lealgorithm.blogspot.jp をマイナーとして含まないグラフは t-彩色可能 なのでしょうか? もしかして対偶とって、t彩色可能でなければ、少なくとものマイナーを含むにすればよい?だとするとそれに含まれる臨界グラフの頂点は全て次数t以上で、頂点数はt+1以…

最大クリークの。。。

最大クリーク数をcとすると、の確率で最大クリークと一致する順序が得られるのか。。。同じサイズの極大クリークあればもっと良い確率になるけど。。とりあえず下記でできる気がしてきた。1. サイズcのクリークは次数c-1以上の頂点がc個必要(条件A)なので、…