DocumentCode :
2263883
Title :
Odd-cycle inequalities, via minimization and LP-completeness
Author :
Titan, Hari S.
Author_Institution :
Dept. of Phys. & Comput., Wilfrid Laurier Univ., Waterloo, Ont., Canada
fYear :
1993
fDate :
16-18 Aug 1993
Firstpage :
194
Abstract :
We report solving odd-cycle inequalities linear programs to obtain Max-Cuts of instances of planar graphs obtained from the via minimization of the circuit layer assignment problem (where electrically common points have degree of at most three) in running times comparable to well-known fast approximate methods. This method does not require graph embeddings in the plane or graph transformations and runs in polynomial time. Furthermore, this odd-cycle LP relaxation of the Max-Cut problem on general graphs is proved to be as intractable as any other Max-Cut LP relaxation with respect to the question of being able to recognize exactly those problem inputs which have a 0-1 optimal solution to the linear program. This serves to strengthen the argument for attempting to solve non-planar Max-Cut problems by solving for the odd-cycle LP relaxation
Keywords :
circuit layout; graph theory; linear programming; minimisation; LP-completeness; circuit layer assignment problem; max-cut LP relaxation; nonplanar max-cut problems; odd-cycle inequalities linear programs; planar graphs; polynomial time; via minimization; Circuits; Linear programming; Minimization methods; Physics computing; Polynomials; Tree graphs; Wires;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1993., Proceedings of the 36th Midwest Symposium on
Conference_Location :
Detroit, MI
Print_ISBN :
0-7803-1760-2
Type :
conf
DOI :
10.1109/MWSCAS.1993.343096
Filename :
343096
Link To Document :
بازگشت