scientific article; zbMATH DE number 7764115

DOI10.4230/LIPICS.IPEC.2020.24MaRDI QIDQ6089671FDOQ6089671

Authors: Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz 

Publication date: 13 November 2023

Title of this publication is not available (Why is that?)

zbMATH Keywords

parameterized complexityreconfigurationconnected dominating setgraph structure theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Linear time solvable optimization problems on graphs of bounded clique-width
• Geometric folding algorithms. Linkages, origami, polyhedra
• Parameterized algorithms
• Deciding first-order properties of nowhere dense graphs
• The \(k\)-dominating graph
• Connectedness of the graph of vertex-colourings
• The complexity of change
• Reconfiguration of dominating sets
• Kernelization using structural parameters on sparse graph classes
• On the parameterized complexity of reconfiguration problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the complexity of reconfiguration problems
• Domination problems in nowhere-dense classes of graphs
• Kernelization and Sparseness: the case of Dominating Set
• Reconfiguration on sparse graphs
• Reconfiguration of list edge-colorings in a graph
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The complexity of dominating set reconfiguration
• Reconfiguration on nowhere dense graph classes
• Introduction to reconfiguration
• Flip distance is in FPT time \(O(n+ k \cdot c^k)\)
• Lossy kernels for connected dominating set on sparse graphs
• Ground state connectivity of local Hamiltonians
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Title not available (Why is that?)
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• On the number of types in sparse graphs
• Flip distance between two triangulations of a point set is NP-complete

Cited In (4)

• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• On the parameterized complexity of reconfiguration problems
• Reconfiguration graphs for dominating sets

This page was built for publication:

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