For a given (unweighted) graph G(V,E) with an integer d > 1. How to find a connected subgraph H of G with maximum |V(H)| and satisfying ∆(H) ≤ d (i.e. subgraph H is connected with the maximum number of nodes in which degree of node in H is bounded by d).
Cound anyone please suggest an approximation algorithm to find the subgraph H with satifying above mentioned constraints?
For d=2 it is the longest path problem, which can not be approximated unless P=NP (see http://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers ).
Dear Michal
Thank you.
Could you please suggest me any approximation algorithm for d ≥ 2 ?
Maybe this will help: http://www-math.mit.edu/~goemans/PAPERS/bmst-focs06.pdf
Ram, I recently found very good Algebra behind Graph Theory. Perhaps you should have a look at their approach. It is more complex in terms of language, but perhaps they have already done a lot there.
Dear Ma'am ,
It would be easier and time saving for me if you could provide me some useful references where they have used the concept of Algebra to solve the above mentioned problem.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs