2011/01/01 by Thore Husfeldt, Dieter Kratsch, Husfeldt, Thore +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms #Completeness (order theory) #Complexity #Complexity and Algorithms in Graphs #Computer science #Exponential Time #Graph Labeling and Dimension Problems #Graphs #Mathematical optimization #Mathematics #NP-hard Problems #SAT #Theoretical computer science #Travelling salesman problem
paper · doi:10.4230/dagsemproc.10441.1
published in DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 0 (Schloss Dagstuhl – Leibniz Center for Informatics)
openalex publication_date 2011/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A decade before NP-completeness became the lens through which Computer Science views computationally hard problems, beautiful algorithms were discovered that are much better than exhaustive search, for example Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem and Ryser's 1963 inclusion--exclusion formula for the permanent.