Finding optimal solutions with neighborly help
DOI10.1007/S00453-023-01204-1zbMATH Open1541.68276MaRDI QIDQ6547211FDOQ6547211
Authors: Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, David Wehner 
Publication date: 30 May 2024
Published in: Algorithmica (Search for Journal in Brave)
computational complexityadvicesatisfiabilityvertex covercolorabilitycritical graphsreoptimizationparallel access to NPdifference polynomial timeminimality problemsstructural self-reducibility
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- The complexity of facets resolved
- Title not available (Why is that?)
- Some Theorems on Abstract Graphs
- The complexity of Kemeny elections
- More complicated questions about maxima and minima, and some closures of NP
- Bounded Query Classes
- On the Hardness of Reoptimization
- Reoptimizing the traveling salesman problem
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Scheduling with forbidden sets
- On the autoreducibility of functions
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Finding Optimal Solutions With Neighborly Help.
- Complexity of stability
- Title not available (Why is that?)
This page was built for publication: Finding optimal solutions with neighborly help
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6547211)
