Exact algorithms for NP-hard problems: A survey

Autor:	Woeginger, Gerhard, Junger, M., Reinelt, G., Rinaldi, G.
Přispěvatelé:	Discrete Mathematics and Mathematical Programming, Stochastic Operations Research
Jazyk:	angličtina
Rok vydání:	2003
Předmět:	Mathematical optimization Knapsack problem Graph coloring METIS-213358 Travelling salesman problem Graph Satisfiability Scheduling (computing) Exponential function Mathematics MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Combinatorial Optimization--Eureka, you shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers, 185-207 STARTPAGE=185;ENDPAGE=207;TITLE=Combinatorial Optimization--Eureka, you shrink! Combinatorial Optimization — Eureka, You Shrink! ISBN: 9783540005803 Combinatorial Optimization-Eureka! You shrink! Papers dedicated to Jack Edmonds. (5th International Workshop, Aussois, France, March 2001, Revised papers), 185-207 STARTPAGE=185;ENDPAGE=207;TITLE=Combinatorial Optimization-Eureka! You shrink! Papers dedicated to Jack Edmonds. (5th International Workshop, Aussois, France, March 2001, Revised papers)
Popis:	We discuss fast exponential time solutions for NP-complete problems. We survey known results and approaches, we provide pointers to the literature, and we discuss several open problems in this area. The list of discussed NP-complete problems includes the travelling salesman problem, scheduling under precedence constraints, satisfiability, knapsack, graph coloring, independent sets in graphs, bandwidth of a graph, and many more.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92420dc397ef587f705d770bc83e84c5 https://research.utwente.nl/en/publications/ac91a928-a94b-4cab-8044-1b27e086ad5c Zobrazit plný text záznamu