Nie jesteś zalogowany | Zaloguj się

I will present an algorithm for the dominating set problem, which

has the following features:

-- is super-simple (and heuristic-like)

-- has a provable polynomial running time on many structural graph

classes (and beyond)

-- is not specific to any particular class of graphs and does not use any

kind of a graph decomposition (ex. no approximation of treewidth

decomposition required)

-- can be generalized to slightly more general problems using logic

-- a similar approach can be applied to the independent set problem

(which is somehow opposite in nature)

Talk will be nowhere dense details free.

Progressive Algorithms for Domination and Independence