Finding optimal solutions with neighborly help

DOI10.1007/S00453-023-01204-1MaRDI QIDQ6547211zbMATH OpenFDO

Authors Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, David Wehner

Publication date 30 May 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

computational complexityadvicesatisfiabilityvertex covercolorabilitycritical graphsreoptimizationparallel access to NPdifference polynomial timeminimality problemsstructural self-reducibility

Mathematics Subject Classification ID

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)

Recommendations

• Finding Optimal Solutions With Neighborly Help.
• scientific article; zbMATH DE number 4024813
• Reducing the chromatic number by vertex or edge deletions
• Critical vertices and edges in \(H\)-free graphs
• Parameterized complexity of vertex colouring

Cites work

• scientific article; zbMATH DE number 3908468 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Bounded Query Classes
• Complexity of stability
• Finding Optimal Solutions With Neighborly Help.
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• More complicated questions about maxima and minima, and some closures of NP
• On the Hardness of Reoptimization
• On the autoreducibility of functions
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimizing the traveling salesman problem
• Scheduling with forbidden sets
• Some Theorems on Abstract Graphs
• The complexity of Kemeny elections
• The complexity of facets resolved

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)