Property Testing in Planar Graphs: Bipartiteness and Subgraph Freeness
Date: Wednesday, February 05, 2020
Time: 3:00 PM to 4:00 PM Note: all times are in the Eastern Time Zone
Location: Seminar Room G575
Event Type: Seminar
Host: Quanquan Liu, Sitan Chen, NIkhil Vyas
Contact: Quanquan Liu, firstname.lastname@example.org
Speaker URL: None
TALK: Property Testing in Planar Graphs: Bipartiteness and Subgraph Freeness
Property testing in planar bounded degree graphs is well understood.
However, the algorithms depend heavily on the assumption that the input
graph has bounded degree and cannot be used for general planar graphs.
In this line of work we study testability of properties of general planar
graphs. We first show that a random walk based approach can be used to
obtain a bipartiteness tester with constant query complexity. Then we
explain a modified random neighborhood exploration that can be used to
test subgraph freeness.
(Joint work with Artur Czumaj, Morteza Monemizadeh and Krzysztof Onak)
Algorithms & Theory
Created by Quanquan Liu at Tuesday, February 04, 2020 at 12:16 PM.