Notices
Results 1 to 1 of 1

Thread: Is the Maximum Independent Set on DAG is NP-Complete ??

  1. #1 Is the Maximum Independent Set on DAG is NP-Complete ?? 
    New Member
    Join Date
    Dec 2009
    Posts
    2
    I am wondering if Maximum Independent Set on DAG is NP-Complete problem. I know that if the graph is undirected then it is an NP-Complete, but what about DAGs.. Please help by a proof...


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •