A Separator Theorem for Planar GraphsとOn Sparse Graphs with Dense Long Pathsを読む。 ちょっとずつまとめていく。 On Sparse Graphs with Dense Long Paths 論文の主定理は以下の通り どんな頂点を取り除いても長さのPathが残るようなDAGの辺数をとし…

e-archive.informatik.uni-koeln.de を読んだ。 https://icpc-girigiri.slack.com/archives/GJM417MNV/p1566016527000100 にファイルがある。 概要 平面グラフのmax-cutをmaximum weighted matchingに帰着させて解いている。平面グラフのmaximum weighted ma…