### ?

## Reusing the Same Coloring in the Child Nodes of the Search Tree for the Maximum Clique Problem

Lecture Notes in Computer Science. 2015. Vol. 8994. P. 275-280.

In this paper we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value δ. The obtained increase in performance reaches 70 % on benchmark instances.

Mikhail Batsyn, Boris Goldengorin, Evgeny Maslov et al., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 397-416

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast ...

Added: February 17, 2013

San Segundo P., Nikolaev A., Batsyn M., Computers & Operations Research 2015 Vol. 64 P. 293-303

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 ...

Added: August 24, 2015

А. И. Николаев, Информационные технологии 2016 Т. 22 № 4 С. 249-254

In this paper a new approach for solving the maximum clique problem is presented. For a given graph the suggested approach uses machine learning technique to predict the fastest algorithm from several algorithms for the maximum clique problem. Then the chosen algorithm is applied for solving the maximum clique problem in this graph. The computational ...

Added: May 27, 2016

Babkina T. S., Demidovskij A., Babkin E., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155

This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach ...

Added: October 3, 2018

Voloshinov V., Smirnov S., Sukhoroslov O. V., Procedia Computer Science 2017 Vol. 108 P. 1532-1541

This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent ...

Added: August 30, 2018

Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, Journal of Global Optimization 2014 Vol. 59 No. 1 P. 1-21

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 ...

Added: May 24, 2013

Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, , in : Models, Algorithms, and Technologies for Network Analysis. Vol. 59.: NY : Springer, 2013. Ch. 7. P. 93-99.

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 ...

Added: November 19, 2013

Malyshev D., Pardalos P. M., Optimization Letters 2015 Vol. 9 No. 5 P. 839-843

The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure
of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss ...

Added: September 26, 2014

Utkina I. E., / Cornell University Library. 2017.

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 Ostergard's algorithm ...

Added: October 15, 2017

Ulyanov M., Fomichev M., Головешкин В. А. et al., 2017 Т. 13 № 1 С. 19-24

The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions ...

Added: September 26, 2017

Batsyn M.V., Kalyagin V.A., Tulyakov D. N., / Институт прикладной математики им. М.В. Келдыша Российской академии наук. 2015. No. 91.

The Protein Structure Alignment Problem (PSAP) consists in finding the
best alignment of two proteins defined by their primary structures. It finds
the most similar substructure of two proteins. This problem is polynomially
reducible to the Maximum Clique Problem (MCP) for the protein alignment
graph. In this paper we present an efficient algorithm for the PSAP based on
our recent ...

Added: October 24, 2016

Kiselyova N. N., Dudarev V.A., Korzhuev M. A., Inorganic Materials: Applied Research 2016 Vol. 7 No. 1 P. 34-39

A database (DB) on the bandgap of inorganic substances available via the Internet (http://bg.imetdb.ru) was developed for the information service of specialists in the sphere of inorganic chemistry and materials science. The DB is integrated with other information systems on the properties of inorganic substances and materials, which provides the search of a wide range ...

Added: February 23, 2016

Baibikova T., Domoratsky E., Вестник Московского финансово-юридического университета 2017 № 1 С. 200-206

Some questions of scientific visualization are under consideration in this paper. This article also discusses the peculiarities of application of cognitive computer graphics, singles out a range of tasks of scientific visualization. The paper gives a brief overview of modern support tools for program visualization, tendencies of their development and their main characteristics. A module ...

Added: June 10, 2017

Toldova S., Azerkovich I., Гришина Ю. et al., / НИУ ВШЭ. Series WP BRP "Linguistics". 2015.

Building benchmark corpora in the domain of coreference and anaphora resolution is an important task for developing and evaluating NLP systems and models. Our study is aimed at assessing the feasibility of enhancing corpora with information about coreference relations. The annotation procedure includes identification of text segments that are subjects to annotation (markables), marking their ...

Added: December 15, 2015

Kalyagin V.A., Koldanov A.P., Koldanov P.A. et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59-70

A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...

Added: July 19, 2014

Vishnekov A., Erokhin V., Ivanova E., Датчики и системы 2018 Т. 221 № 1 С. 18-24

The article discusses the recovery of distributed control systems of technical objects. The options for the design of subsystems recovery after hardware or software fault of the sensor system are investigated. The development of an integrated subsystems recovery is proposed on the basis of decision-making system to develop the most rational control actions by ...

Added: January 27, 2018

М. : National Instruments Russia, 2017

Содержание сборника составляют доклады с результатами оригинальных исследований и технических решений, ранее не публиковавшиеся. Мы надеемся, что предлагаемый сборник окажется полезным для специалистов, работающих в различных областях науки и техники, для широкого круга преподавателей, аспирантов и студентов ВУЗов, а также для преподавателей средних школ и технических колледжей. ...

Added: May 10, 2017

Furmanov K. K., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253

Added: December 22, 2016

Decrouez G. G., Hall P., Bernoulli: a journal of mathematical statistics and probability 2013 Vol. 19 No. 4 P. 1268-1293

Motivated by a problem arising when analysing data from quarantine searches, we explore properties of distributions of sums of independent means of independent lattice-valued random variables. The aim is to determine the extent to which approximations to those sums require continuity corrections. We show that, in cases where there are only two different means, the ...

Added: September 29, 2014

ООО Фирма "Элист", 2014

В книге представлены тезисы докладов I тура XV Всероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов. ...

Added: October 17, 2014

Barcelona : International Association of Technology, Education and Development , 2012

Added: September 11, 2012

Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189

The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...

Added: January 28, 2020

Karpov V. E., Karpova I. P., Procedia Engineering 2015 Vol. 100 P. 1459-1468

Work solutions are proposed for problems of leader definition and role distribution in homogeneous groups of robots. It is shown that transition from a swarm to a collective of robots with hierarchical organization is possible using exclusively local interaction. The local revoting algorithm is central to the procedure for choice of leader while redistribution of roles can ...

Added: March 14, 2015

Shuranov E., / Cornell University. Series Computer Science "arxiv.org". 2021.

Text encodings from automatic speech recognition (ASR) transcripts and audio representations have shown promise in speech emotion recognition (SER) ever since. Yet, it is challenging to explain the effect of each information stream on the SER systems. Further, more clarification is required for analysing the impact of ASR's word error rate (WER) on linguistic emotion ...

Added: February 14, 2023