I got this mail.... Dear Praveen Sonare,
the hamiltonian circuit (HC) problem remains NP-complete when restricted to chordal bipartite graphs (cbg) and becomes polynomial when restricted further to bipartite distance hereditary graphs (bdhg). I'm not aware of any "well established" class of graphs between bdhg and cbg. If there is one, you could consider the computational complexity of HC when restricted to this class. Do you have any such class of graphs in mind? With kind regards, Haiko. I dont have anything else... nothing is striking in my mind... On Sun, Mar 8, 2009 at 9:34 AM, sharad kumar <aryansmit3...@gmail.com>wrote: > pls give clear question yaar...... > > > On Sun, Mar 8, 2009 at 2:43 AM, Miroslav Balaz <gpsla...@googlemail.com>wrote: > >> can you also provide description of bdhg,cbg or hyperlink to them. >> Is this question hard? I am not graph expert. >> >> 2009/3/7 Monty <praveensonare...@gmail.com> >> >> >>> the hamiltonian circuit (HC) problem remains NP-complete when >>> restricted to chordal bipartite graphs (cbg) and becomes polynomial >>> when restricted further to bipartite distance hereditary graphs >>> (bdhg). I'm not aware of >>> any "well established" class of graphs between bdhg and cbg. If there >>> is one, you could consider the computational complexity of HC when >>> restricted to this class. Do you have any such class of graphs in >>> mind? >>> >>> anybody having any idea??? >>> please help me..... >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
