Сибирский федеральный университет

Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций

Конференция: 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 preprocessing 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

• Bykova Valentina (Siberian Fed Univ, Inst Math & Comp Sci, Krasnoyarsk 660041, Russia)
• Illarionov Roman (Siberian Fed Univ, Inst Math & Comp Sci, Krasnoyarsk 660041, Russia)

• Web of Science Core Collection
• Scopus
• Ядро РИНЦ (eLIBRARY.RU)