Progressive algorithms for domination and independence

DOI10.4230/LIPICS.STACS.2019.27MaRDI QIDQ5090476FDOQ5090476

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

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

zbMATH Keywords

stabilitydominating setfixed-parameter tractabilityindependent setnowhere denseness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (10)

• 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
• Bounds on half graph orders in powers of sparse graphs
• Title not available (Why is that?)
• Constant round distributed domination on graph classes with bounded expansion
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

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)