Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

Revision as of 02:11, 13 November 2007

2. A sub-optimal solution to TSP is a Hamiltonian Cycle.

4. Finding disjoint paths with different path-costs: Complexity and algorithms

Randeep Bhatia · Murali Kodialam · T. V. Lakshman, "Finding disjoint paths with related path costs", Springer Science+Business Media, LLC 2006

Bin Zhang, Julie Ward, Qi Feng, "Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing", HP Laboratories Palo Alto, June 28, 2005
J. M. W. Rhys, "A Selection Problem of Shared Fixed Costs and Network Flows", Management Science, Vol. 17, No. 3, Theory Series (Nov., 1970), pp. 200-207

@@ Line 8: / Line 8: @@
 :1. [http://www.soe.ucsc.edu/classes/cmps132/Winter05/hw/hw8sols.pdf 2-SAT is in NP]
 :2. A sub-optimal solution to TSP is a Hamiltonian Cycle.
+:3. [http://www.cit.gu.edu.au/teaching/3130CIT/lectures/complexity.pdf 3SAT reduction to NAESAT]
 :4. Finding disjoint paths with different path-costs: Complexity and algorithms
 *Randeep Bhatia · Murali Kodialam · T. V. Lakshman, [http://www.springerlink.com.ezproxy1.lib.asu.edu/content/x24w933w7vgu262x/fulltext.pdf "Finding disjoint paths with related path costs"], Springer Science+Business Media, LLC 2006