zbMATH — the first resource for mathematics

Real-time systems: incomplete solution approach for the maximum-weighted clique problem. (English) Zbl 1157.68406
Gammerman, A. (ed.), Artificial intelligence and applications. Machine learning. As part of the 26th IASTED international multi-conference on applied informatics. Calgary: International Association of Science and Technology for Development (IASTED); Anaheim, CA: Acta Press (ISBN 978-0-88986-710-9/CD-ROM). 140-145 (2008).
Summary: 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.
For the entire collection see [Zbl 1154.68012].

68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms