Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs.
Kaveh KhoshkhahMehdi Khosravian GhadikolaeiJérôme MonnotDirk Oliver TheisPublished in: Theor. Comput. Sci. (2019)
Keyphrases
- decision problems
- pspace complete
- np complete
- special case
- problems involving
- application domains
- computational issues
- genetic algorithm
- closely related
- graph theoretic
- computationally hard
- polynomial time complexity
- polynomial hierarchy
- np hardness
- specific problems
- convex functions
- graph matching
- computational cost
- pairwise