Abstrakt. En exakt lösningsmetod för grafbisektionsproblemet presenteras. Vi beskriver en gren-och-bunden algoritm som är baserad på en skärande plan strategi som kombinerar semide nite programmering och polyhedral avkopplingar. Vi rapporterar om omfattande numeriska experiment som utfördes för olika klasser av grafer. Resultaten visar att det nuvarande tillvägagångssättet löser allmänna problemfall med 80? 90 hörn exakt i rimlig tid, och ger snäva approximationer för större fall. Vårt tillvägagångssätt är särskilt väl lämpat för speciella klasser av grafer som plana grafer och grafer baserade på rutnätsstrukturer.
Karisch, Rendl, och Clausen REF lösa graf bidelning problem till optimalitet med en gren-och-bundet metod baserat på en skärplan strategi som kombinerar semidefinit och polyhedral avkopplingar.
Solving Graph Bisection Problems with Semidefinite Programming
{'venue': 'INFORMS Journal on Computing', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}