Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: International Scientific Conference on Information Technologies and Mathematical Modelling (ITMM); Anzhero Sudzhensk, RUSSIA; Anzhero Sudzhensk, RUSSIA
Год издания: 2014
Идентификатор DOI: 10.2147/PPA.S72004
Ключевые слова: Graph algorithms, sparse graphs, decomposition graph, atom graph, preprocessing, biphasic algorithms, treewidth, FPT-algorithms, Algorithms, Atoms, Mathematical models, Clique problems, Exact solution, Large dimensions, Maximum clique problems, Tree-width, Graph theory
Аннотация: In this paper the NP-hard Maximum Clique Problem (MCP) is considered. It is supposed that the input graph is sparse. Also, it is believed that the input graph can have a huge number of vertices. A biphasic algorithm for finding the exact solution of the MCP is proposed in the paper. The first phase of the algorithm is the preprocesПоказать полностьюsing of the input graph by decomposing it into atoms. The second phase of the algorithm reduces to an application for each atom classical algorithm Wilf and then to the formation of solutions for the graph as a whole. The level of sparseness of the input graph is given in the form of restrictions on its treewidth. It have been proved that the running time of biphasic algorithm is polynomial in the number of vertices and the exponential of the treewidth of the input graph.
Журнал: INFORMATION TECHNOLOGIES AND MATHEMATICAL MODELLING
Выпуск журнала: Vol. 487
Номера страниц: 69-75
ISSN журнала: 18650929
Место издания: BERLIN
Издатель: SPRINGER-VERLAG BERLIN