Can local optimality be used for efficient data reduction?
From MaRDI portal
Publication:2692734
DOI10.1007/978-3-030-75242-2_25OpenAlexW3158282794MaRDI QIDQ2692734
Christian Komusiewicz, Nils Morawietz
Publication date: 22 March 2023
Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_25
Uses Software
Cites Work
- The parameterized complexity of local search for TSP, more refined
- The disjoint paths problem in quadratic time
- Local search: is brute-force avoidable?
- A simplified NP-complete satisfiability problem
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- How easy is local search?
- Independent-set reconfiguration thresholds of hereditary graph classes
- Distributed reconfiguration of maximal independent sets
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Extension and its price for the Connected Vertex Cover problem
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Complexity of Independent Set Reconfiguration on Bipartite Graphs
- NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
- Independent set reconfiguration parameterized by modular-width