А.Н. Воропаев

Учёт обхвата при подсчёте коротких циклов в двудольных графах

Рассмотрены пять методов подсчёта циклов в двудольных графах с длиной, близкой к обхвату. Для явных формул показано, что наиболее трудоёмкой операцией оказывается умножение матриц, если длины подсчитываемых циклов не превышают удвоенного обхвата. Детально обсуждаются количество матриц и матричных умножений, участвующих в расчётах с использованием явных выражений и алгоритма «леденцов» (которые имеют одинаковые порядки сложности). Выполнено сравнение вычислительных затрат всех методов в случае подсчёта циклов длиной до удвоенного обхвата в графах различной плотности. В частности, указаны оценки плотности графов, при которой алгоритмы, ориентированные на разреженную структуру, работают эффективнее «матричных» методов.

 

КЛЮЧЕВЫЕ СЛОВА: подсчёт циклов в двудольных графах, умножение матриц, алгоритм «леденцов», оценки плотности графов