Finding Optimal Solutions With Neighborly Help.

DOI10.4230/LIPICS.MFCS.2019.78MaRDI QIDQ5092442zbMATH OpenOpenAlexFDO

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

Publication date 21 July 2022

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

zbMATH Keywords

computational complexitysatisfiabilityvertex covercolorabilitycritical graphsminimality problemsreoptimizatstructural self-reducibility

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 867627 (Why is no real title available?)
• Bounded Query Classes
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• More complicated questions about maxima and minima, and some closures of NP
• 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
• Turán's theorem and k‐connected graphs

Cited in

(4)

• Complexity of Stability.
• Complexity of stability
• More neighbors, more efficiency
• Finding optimal solutions with neighborly help

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 Q5092442)