The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

 
       
         
    STUDIA INFORMATICA - Issue no. 2 / 2004  
         
  Article:   A NOTE ON THE COMPLEXITY OF THE GENERALIZED MINIMUM SPANNING TREE PROBLEM.

Authors:  CORINA POP SITAR, PETRICĂ C. POP.
 
       
         
  Abstract:  We consider the Generalized Minimum Spanning Tree Problem denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding the complexity of the problem, namely, the GMST problem even on trees is NP-hard. As well as we present three cases when the GMST problem is solvable in polynomial time.  
         
     
         
         
      Back to previous page