scientific article
From MaRDI portal
Publication:3701213
zbMath0578.90087MaRDI QIDQ3701213
David S. Johnson, Christos H. Papadimitriou
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
surveycomputational complexityNP-completenessspanning treeconvex polytopespolynomial reductionsTraveling Salesman Problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (5)
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Efficient web searching using temporal factors ⋮ A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem ⋮ On the complexity of postoptimality analysis of \(0/1\) programs
This page was built for publication:
