Back to Results
First PageMeta Content
Spanning tree / NP-complete problems / Operations research / Travelling salesman problem / Graph operations / Minimum spanning tree / Graph / Planar graph / Eulerian path / Graph theory / Theoretical computer science / Mathematics


6.889 — Lecture 15: Traveling Salesman (TSP) Christian Sommer (figures by Philip Klein) November 2, 2011 Traveling Salesman Problem (TSP) given G = (V, E) find a tour visiting each1 node v ∈ V . NP–har
Add to Reading List

Document Date: 2011-11-29 11:50:24

Open Document

File Size: 559,90 KB

Share Result on Facebook

Company

SIAM Journal / /

/

Facility

Carnegie Mellon University / /

Holiday

Assumption / /

IndustryTerm

feasible solution / earlier algorithms / polynomial-time algorithm / optimum solution / /

Organization

Graduate School / Industrial Administration / Carnegie Mellon University / /

Person

Philip N. Klein / David R. Karger / David S. Johnson / Michelangelo Grigni / Michael R. Garey / Sanjeev Arora / Mohit Singh / Philip Klein / Christos H. Papadimitriou / Ola Svensson / Amin Saberi / Elias Koutsoupias / Andrzej Woloszyn / Shayan Oveis Gharan / Santosh Vempala / Robert Endre Tarjan / Christian Sommer / /

Position

Traveling Salesman / References The Traveling Salesman / Salesman / /

ProgrammingLanguage

E / C / TSP / /

PublishedMedium

SIAM Journal on Computing / Theory of Computing / /

Technology

polynomial-time algorithm / unit-length graphs Algorithm / 2 Spanner Problem Algorithm / /

URL

http /

SocialTag