2011/01/01 by Thore Husfeldt, Dieter Kratsch, Husfeldt, Thore +5
Computer Science · #Advanced Graph Theory Research #Algorithms #Complexity #Complexity and Algorithms in Graphs #Exponential Time #Graph Labeling and Dimension Problems #Graphs #NP-hard Problems #SAT
paper · doi:10.4230/dagsemproc.10441.1
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.