REAL-TIME SYSTEMS: INCOMPLETE SOLUTION APPROACH FOR THE MAXIMUM-WEIGHTED CLIQUE PROBLEM

摘要

In this paper we are reviewing how the maximum-weight clique problem is solved in the real-time systems' environment by the best-known algorithms. The real-time environment is a quite unique one applying interesting restrictions on algorithms to be used and is rarely considered by researches although a lot of applications are hosted there. The main conflict to be researched here is produced by a time complexity of the maximum-weight clique problem and the real-time systems' requirement to solve a case during a predefined time interval. In this article an "incomplete solution" approach is used to explore maximum-weight clique algorithms performance.