Finding Optimal Solutions With Neighborly Help.

DOI10.4230/LIPIcs.MFCS.2019.78OpenAlexW2970391455MaRDI QIDQ5092442

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

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1906.10078

zbMATH Keywords

computational complexitycolorabilitycritical graphssatisfiabilityvertex coverminimality problemsreoptimizatstructural self-reducibility

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Complexity of stability, Complexity of Stability.

Cites Work

• 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
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• Bounded Query Classes
• Reoptimizing the traveling salesman problem
• Turán's theorem and k‐connected graphs
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Some Theorems on Abstract Graphs
• Scheduling with forbidden sets
• Unnamed Item
• Unnamed Item
• Unnamed Item