b-matchingというものを知った。 グラフが与えられたとき、次の条件を満たす辺集合はb-matchingであるという。 各頂点のdegree restrictionをとし、各辺のcapacity が与えられる。このとき各辺についてcapacity以下の重みをとって、各頂点について隣接する辺…

A separator theorem for minor-closed classes を読むと、minor-closedなグラフはのseparatorを持つのでは？という話がされている。この論文では実際に、をminorとして含まないようなグラフについて、のseparatorを持つことを証明している。 したがって、bo…