Using modular decomposition technique to solve the maximum clique problem
In this article we use the modular decomposition technique for exact solving the weighted maximum clique problem. Our algorithm takes the modular decomposition tree from the paper of Tedder et. al. and finds solution recursively. Also, we propose algorithms to construct graphs with modules. We show some interesting results, comparing our solution with Ostergards algorithm on DIMACS benchmarks and on generated graphs.
A simple measure of similarity for the construction of the market graph is proposed. The measure is based on the probability of the coincidence of the signs of the stock returns. This measure is robust, has a simple interpretation, is easy to calculate and can be used as measure of similarity between any number of random variables. For the case of pairwise similarity the connection of this measure with the sign correlation of Fechner is noted. The properties of the proposed measure of pairwise similarity in comparison with the classic Pearson correlation are studied. The simple measure of pairwise similarity is applied (in parallel with the classic correlation) for the study of Russian and Swedish market graphs. The new measure of similarity for more than two random variables is introduced and applied to the additional deeper analysis of Russian and Swedish markets. Some interesting phenomena for the cliques and independent sets of the obtained market graphs are observed.
This book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017.
The 31 full papers presented in this volume were carefully reviewed and selected from 71 submissions. They cover a wide range of areas, aiming at connecting theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. Another focus is on presenting recent results and on identifying and exploring promising directions of future research.
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.
The approaches based on applying of metamodeling and domain-specific languages are widely used in software engineering. There are many different tools for creating visual domain-specific modeling languages with a possibility of determining user’s graphical notations. However, these tools possess disadvantages. The article presents an approach to the development of language workbench that allows to eliminate some restrictions of existing DSM-platforms. The MetaLanguage system is designed for creation of visual dynamic adaptable domain-specific modeling languages and for models construction with these languages. It allows executing transformations of the created models in various textual and graphical notations. Basic metalanguage constructions of this system are described. The formal description of modeling languages metamodel used in MetaLanguage is given. The architecture of MetaLanguage toolkit is presented.
In this chapter, we present our enhancements of one of the most efficient exact algorithms for the maximum clique problem—MCS algorithm by Tomita, Sutani, Higashi, Takahashi and Wakatsuki (in Proceedings of WALCOM’10, 2010, pp. 191–203). Our enhancements include: applying ILS heuristic by Andrade, Resende and Werneck (in Heuristics 18:525–547, 2012) to find a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial coloring, and avoiding dynamic memory allocation. A good initial solution considerably reduces the search tree size due to early pruning of branches related to small cliques. Fast detecting of clique vertices is based on coloring. Whenever a set of candidates contains a vertex adjacent to all candidates, we detect it immediately by its color and add it to the current clique avoiding unnecessary branching. Though dynamic memory allocation allows to minimize memory consumption of the program, it increases the total running time. Our computational experiments show that for dense graphs with a moderate number of vertices (like the majority of DIMACS graphs) it is more efficient to store vertices of a set of candidates and their colors on stack rather than in dynamic memory on all levels of recursion. Our algorithm solves p_hat1000-3 benchmark instance which cannot be solved by the original MCS algorithm. We got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances, correspondingly.
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.
Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even tighter bounds by reducing each colored subproblem to maximum satisfiability problem (MaxSAT). Moreover they show empirically that the new bounds obtained may be lower than the chromatic number.
Based on this idea this paper shows an efficient way to compute related “infra-chromatic” upper bounds without an explicit MaxSAT encoding. The reported results show some of the best times for a stand-alone computer over a number of instances from standard benchmarks.