Progressive algorithms for domination and independence

DOI10.4230/LIPICS.STACS.2019.27MaRDI QIDQ5090476zbMATH OpenFDO

Authors Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1811.06799

zbMATH Keywords

stabilitydominating setfixed-parameter tractabilityindependent setnowhere denseness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Domination problems in nowhere-dense classes of graphs
• FPT algorithms for domination in sparse graphs and beyond
• Polynomial kernels and wideness properties of nowhere dense graph classes
• On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs

Cites work

• Approximation algorithms for independent sets in map graphs
• Classification theory and the number of non-isomorphic models.
• Closed sets and chain conditions in stable theories
• Domination problems in nowhere-dense classes of graphs
• FPT algorithms for domination in biclique-free graphs
• First order properties on nowhere dense structures
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Kernelization and Sparseness: the case of Dominating Set
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On nowhere dense graphs
• On the number of types in sparse graphs
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Sparsity. Graphs, structures, and algorithms
• Stable graphs
• Testing first-order properties for subclasses of sparse graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(11)

• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• On the parameterized complexity of reconfiguration of connected dominating sets
• Lossy kernels for connected dominating set on sparse graphs
• Clustering powers of sparse graphs
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• Distributed domination on sparse graph classes
• Bounds on half graph orders in powers of sparse graphs
• Progressive Algorithms for Domination and Independence
• Bounds on half graph orders in powers of sparse graphs
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: Progressive algorithms for domination and independence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090476)