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

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

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

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

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

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