A Sublinear Tester for Outerplanarity
03/05/2018 - 12:00
Speaker:
Reut Levi
Seminar:
מיקום:
Building 216 room 201
Abstract:
We consider one-sided error property testing of $\calF$-minor freeness in bounded-degree graphs for any finite family of graphs $\calF$ that contains a minor of $K_{2,k}$, the $k$-circus graph, or the $(k\times 2)$-grid for any $k\in\mathbb{N}$.
This includes, for instance, testing whether a graph is outerplanar or a cactus graph.
This is joint work with Hendrik Fichtenberger, Yadu Vasudev and Maximilian Wötzel.
- תאריך עדכון אחרון: 1/05/2018