Исследуются кликовые покрытия рёбер графа. Описаны графы, имеющие единственное кликовое покрытие рёбер, рассмотрена возможность снижения порядка (сжатия) графа с сохранением структуры покрытия, приведены методы, упрощающие процедуру поиска минимального кликового покрытия рёбер, исследована взаимосвязь между изоморфизмами графов и соответствующих сжатых графов.
Скачать электронную версию публикации
Загружен, раз: 238
- Title Исследование кликовых покрытий рёбер графа
- Headline Исследование кликовых покрытий рёбер графа
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(19)
- Date:
- DOI
Ключевые слова
NP-complete problems, graph isomorphism, edge clique covering, graphs, NP-полные задачи, изоморфизм графов, кликовое покрытие рёбер, графы, покрытия графов кликамиАвторы
Ссылки
Харари Ф. Теория графов М.: Мир, 1973. 301с.
Cavers M. S. Clique partitions and coverings of graphs. Masters thesis, University of Waterloo, 2005. http://www.math.uwaterloo.ca/co/graduate-students/files/mmath/ Mike-Cavers.pdf
Gramm J., Guo J., Huffner F., and Niedermeier R. Data reduction, exact, and heuristic algorithms for clique cover // Proc. 8th Workshop on Algorithm Engineering and Experiments, Miami, Fl. January 21, 2006. P. 86-94.
Kou L.T., Stockmeyer L. J., and Wong C. K. Cliques with regard to keyword conflicts and intersection graphs // Comm. ACM. 1978. V.21. No. 2. P. 135-139.
Orlin J. Contentment in graph theory: covering graphs with cliques // Indagat. Math. 1977. No. 39. P. 406-424.
Исследование кликовых покрытий рёбер графа | Прикладная дискретная математика. 2013. № 1(19).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 230