Analysis of Complex Networks

12.7 Conclusion

In this paper, an interesting graph coloring problem was introduced. It was shown that the problem has useful applications to scheduling and location problems. Next, a parameterized family CLC(X) of subproblems of the CLC problem was defined. In Section 12.5, a complexity analysis was performed for eight problems from that infinite family. For five of them, efficient algorithms for their exact solution were presented and analyzed, while the remaining three problems turned out to be NP-complete. And as the reader could observe, graph structure is a significant factor affecting the complexity of a CLC problem.

Finally, from Section 12.6 we learned that those eight problems constitute a uniquely determined complete basis system for the family of problems CLC(X). Knowing such a basis system enables one to easily determine the complexity of any other problem from this family.

The question is: what further research could be done for this particularly interesting problem?

To begin with, it is worth mentioning that, although the complexity classification presented in this paper for the family of problems CLC(X) iscomplete, this does not exclude the possibility of performing a similar complexity classification of some other families of problems determined for other collections of key parameters, or even for other types of constraints imposed on the same key parameters. For instance, in this paper parameters Δ_G, Δ_V,C, and Δ_C,V were bounded from above, and the NP-completeness ...