AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

For a graph G, the problem of deleting a minimum set of nodes of G, such that no graph from a set F of graphs is contained as a minor in G, is known as F-Deletion or F-Minor Cover. The treewidth-3 modulator problem asks for the smallest set S of nodes in a graph G, such that deleting S from G yields a graph with treewidth less than 3. In this thesis we look at two parameterized algorithms for F-Deletion and analyze the specific case where F is the 4-clique K4. These algorithms solve the treewidth-3 modulator problem, as the K4 is the treewidth 3 forbidden minor. One algorithm is deterministic and parameterized by the treewidth of the input graph, and the other one is a randomized algorithm parameterized by the solution size.

Roohani Sharma

+49 681 9325 1116

Zoom

passcode not visible

logged in users only

If you wish to attend the talk, please contact Roohani Sharma rsharma@mpi-inf.mpg.de for the password.