Finding 3-swap-optimal independent sets and dominating sets is hard

DOI10.4230/LIPICS.MFCS.2022.66MaRDI QIDQ6584069FDOQ6584069

Authors: Christian Komusiewicz, Nils Morawietz 

Publication date: 6 August 2024

Recommendations

• An Efficient Local Search for the Minimum Independent Dominating Set Problem
• On the complexity of local search for weighted standard set problems
• Simple Local Search Problems that are Hard to Solve

zbMATH Keywords

local searchgraph problemsPLS-completeness3-swap neighborhood

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Finding 3-swap-optimal independent sets and dominating sets is hard

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