Concept
Planarization
Publications associées (30)
Motif Cut Sparsifiers
Mikhail Kapralov, Mikhail Makarov, Jakab Tardos
A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...
IEEE COMPUTER SOC2022Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022Exceptional graphs for the random walk
If W is the simple random walk on the square lattice Z(2), then W induces a random walk W-G on any spanning subgraph G subset of Z(2) of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, -x, y, -y}, the walk W-G star ...
INST MATHEMATICAL STATISTICS2020