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

dominating setfixed-parameter tractabilityindependent setnowhere densenessstability

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
• First order properties on nowhere dense structures
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• FPT algorithms for domination in biclique-free 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

(23)

• Constant round distributed domination on graph classes with bounded expansion
• Clustering powers of sparse graphs
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Bounds on half graph orders in powers of sparse graphs
• Lossy kernels for connected dominating set on sparse graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Progressive Algorithms for Domination and Independence
• Bounds on half graph orders in powers of sparse graphs
• Distributed domination on sparse graph classes
• On solution discovery via reconfiguration
• Strong odd colorings in graph classes of bounded expansion
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs
• Computing complexity measures of degenerate graphs
• Parameterized covering in semi-ladder-free hypergraphs
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• On first-order transductions of classes of graphs
• Structural parameterizations of the biclique-free vertex deletion problem
• A survey on the parameterized complexity of reconfiguration problems
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• FPT approximation of generalised hypertree width for bounded intersection hypergraphs
• The tape reconfiguration problem and its consequences for dominating set reconfiguration
• On the parameterized complexity of reconfiguration of connected dominating sets

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)