Publication:3701213
From MaRDI portal
zbMath0578.90087MaRDI QIDQ3701213
Christos H. Papadimitriou, David S. Johnson
Publication date: 1985
survey; computational complexity; NP-completeness; spanning tree; convex polytopes; polynomial reductions; Traveling Salesman Problem
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
90C10: Integer programming
68R10: Graph theory (including graph drawing) in computer science
90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
Related Items
Efficient web searching using temporal factors, 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, A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, On the complexity of postoptimality analysis of \(0/1\) programs