home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2460 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.3 KB  |  31 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!caen!zaphod.mps.ohio-state.edu!rpi!chaudhus
  3. From: chaudhus@rolls.cs.rpi.edu (Samit Chaudhuri)
  4. Subject: Re: The P=NP question (was Re: NP Completeness Question
  5. Message-ID: <0ay1n4k@rpi.edu>
  6. Nntp-Posting-Host: rolls.cs.rpi.edu
  7. Organization: Rensselaer Polytechnic Institute, Troy, NY
  8. References: <Bxpv45.2I1@watserv1.uwaterloo.ca>
  9. Date: Wed, 18 Nov 1992 22:38:30 GMT
  10. Lines: 19
  11.  
  12. The Research Report CIS92-D4 by Gismondi, S.J. and Swart E. R. that gives a
  13. polynomial time algorithm to the graph isomorphism problem doesn't make a 
  14. point very clear:
  15.  
  16. In Theorem 1 it proves that every extreme point of the formulation F3 
  17. corresponds to,
  18.   a) An extreme point of C0, the convex hull of all the doubly 
  19.      stochastic Q matrices (Note that they do not necessarily represent an 
  20.      isomorphism between the graphs under consideration. The additional 
  21.      constraints Ta = b are required to ensure that.), or
  22.   b) A convex combination of an extreme point of C0 and a point in 
  23.      C1 (the feasible region of formulation F1)
  24.  
  25. In Corollary 1 it says that the same is also valid for the formulation F4 
  26. (F4 satisfies all the constraints of F3 together with the additional 
  27. constraint Ta = b). Would the new constraint necessarily preserve the 
  28. properties of F3 ?
  29.  
  30. It didn't seem obvious to me, could anyone explain ?
  31.