Finding optimal solutions with neighborly help
DOI10.1007/S00453-023-01204-1zbMATH Open1541.68276MaRDI QIDQ6547211
Elisabet Burjons, Edith Hemaspaandra, Dennis Komm, David Wehner, Fabian Frei
Publication date: 30 May 2024
Published in: Algorithmica (Search for Journal in Brave)
computational complexitycolorabilitycritical graphssatisfiabilityadvicevertex coverreoptimizationparallel 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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of Kemeny elections
- On the autoreducibility of functions
- More complicated questions about maxima and minima, and some closures of NP
- The complexity of facets resolved
- Complexity of stability
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Bounded Query Classes
- Reoptimizing the traveling salesman problem
- Finding Optimal Solutions With Neighborly Help.
- On the Hardness of Reoptimization
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Some Theorems on Abstract Graphs
- Scheduling with forbidden sets
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)
