Progressive Algorithms for Domination and Independence

摘要: We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. identify two model-theoretic properties lead algorithms, namely variants of the Helly property stability. demonstrate our approach by giving linear-time fixed-parameter algorithms for distance-r dominating set problem (parameterized solution size) in wide variety restricted classes, such as powers nowhere dense map graphs, (for $r=1$) biclique-free graphs. Similarly, independent technique give algorithm on any class. Despite simplicity method, several cases results extend known boundaries tractability considered problems improve best running times.