• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Robust optimization of graph partitioning involving interval uncertainty

Theoretical Computer Science. 2012. Vol. 447. P. 53-61.
Fana N., Zhengb Q. P., Pardalos P. M.

Задача разбиения графа заключается в разделении множества вершин графа на число непустых подмножеств так, чтобы общий вес ребер,  соединяющих различные подмножества сводился  к минимуму. Предшествующие исследования требуют ввода мощностей подмножеств или числа подмножеств  для равнораспределения. В этой статье, проблема формулируется как  Zero-one задача квадратичного программирования без ввода мощностей. Мы также представляем три формулировки  равнозначного Zero-one линейного целого программирования. Из-за его важности в bi – кластеризации  данных,  разбиение двудольных графов также изучается. Для практического применения также описываются несколько новых методов определения  числа подмножеств и мощности. Кроме того, изучается  иерархия разделения и разбиения двудольных графов без переназначения одного множества вершин.