in data structures and algorithms, what is meant by "Exact Graph Algorithms" ? can you give me some examples?
+1
A:
I suppose it refers to whether the algorithm yields a result, that is optimal for a given problem or if it yields "just" an approximative result.
For example, if you are looking in a graph for the shortest path from one node to another, there are a bunch of algorithms (Dijkstra, Floyd-Warshall,... you name them) that solve the problem exactly, i.e. they yield a shortest path between the two given nodes.
On the other hand, consider the Travelling Salesman problem. It states the question of a shortest circular path containing some given nodes. This problem is NP-complete, and thus (supposedly) not solvable exactly in a reasonable amount of time (at least for the general case). However, there exist approximation algorithms running in reasonable amount of time, that yield a solution that is at most 2*length(best route) (at least for metric TSP), so the solution from this algorithm is not an exact one, but just an approximation.
phimuemue
2010-07-09 05:52:06
Travelling Salesman Problem has fast 'approximation within twice optimal' algorithms only for special cases like the Euclidean version. For general graphs, there is no polynomial time algorithm (unless P=NP) which can find approximate tour to within constant factor of optimal.
Moron
2010-07-09 05:58:04
The twice optimal construction requires only the very reasonable restriction that the distances are symmetry and satisfy the triangle inequality. (In other words that the distances satisfy axioms of a metric space.) If the distances can be just anything, then asking for a solution within a constant factor of optimal is hardly different from asking for an optimal solution.
Greg Kuperberg
2010-07-09 06:45:12