tag:blogger.com,1999:blog-3722233.post5888730499749403077..comments2024-09-12T13:59:27.670-05:00Comments on Computational Complexity: More on Graph MinorsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-40585828222286894222008-01-27T12:13:00.000-06:002008-01-27T12:13:00.000-06:00Concerning Robertson-Seymour O(n^3) algorithm for ...Concerning Robertson-Seymour O(n^3) algorithm for H-minor testing problem there is another fact that I encountered in Schrijver's Combinatorial Optmization. He says<BR/>that the correctness of this algorithm is based on validity of a lemma which proof is still unpublished.... <BR/>VahanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55000619143218385082008-01-27T09:54:00.000-06:002008-01-27T09:54:00.000-06:00Replying to 2.: I thought that Robertson and Seymo...Replying to 2.: I thought that Robertson and Seymour had already provided a polynomial-time algorithm, in the sense that we can check for any fixed excluded minor in O(n^3), although with an astronomical constant hidden in the O. <BR/><BR/>CrisAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4221555600027847822008-01-26T06:40:00.000-06:002008-01-26T06:40:00.000-06:00Concerning the result of Reed and Kawarabayashi, I...Concerning the result of Reed and Kawarabayashi, I would like to say that for the first time I heard about that from Jim during the mentioned lectures.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46578669681771351602008-01-25T20:37:00.000-06:002008-01-25T20:37:00.000-06:00Actually the first polynomial-time algorithmic res...Actually the first polynomial-time algorithmic result has been obtained by Demaine, Hajiaghayi,and Kawarabayashi in FOCS'05 which is available online. I'm not sure that the result of Reed and Kawarabayashi is finished and checked.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90132509011571367292008-01-25T17:07:00.000-06:002008-01-25T17:07:00.000-06:00Is there an electronically available version of Ka...Is there an electronically available version of Kawarabayashi and Reed's O(n log n) graph minor result?Anonymousnoreply@blogger.com