scientific article; zbMATH DE number 3646634

zbMATH Open0415.90057MaRDI QIDQ3205014FDOQ3205014

Nicos Christofides

Publication date: 1979

Title of this publication is not available (Why is that?)

zbMATH Keywords

computational complexityheuristicslinear programmingcombinatorial optimizationassignment problemtraveling salesman problemapproximate algorithmsworst-case performancematching problemcomputational aspectsresearch surveybranch-and-bound methodsshortest spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Boolean programming (90C09)

Cited In (8)

• Managing tendupatta leaf logistics: an integrated approach
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• A restricted Lagrangean approach to the traveling salesman problem
• Minimum-weight two-connected spanning networks
• Optimizing over the subtour polytope of the travelling salesman problem
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Two-edge connected spanning subgraphs and polyhedra

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3205014)