COIN-OR::LEMON - Graph Library

Irányítatlan gráfok k-élösszefüggővé irányítása

Különböző irányítási algoritmusok implementálása és összehasonlítása.

Háttér

Nash-Williams tétele szerint egy irányítatlan gráfnak pontosan akkor létezik k-élösszefüggő irányítása, ha a gráf 2k-élösszefüggő. Egy jó irányítás megtalálására több algoritmus is született, melyekből néhány az eredetinél általánosabb feladatokra is alkalmazható. Érdekes kérdés, hogy a gyakorlatban melyik megközelítés mennyire hatékony.

Feladat

A feladat ezen algoritmusok közül minél több hatékony implementálása, esetleg speciális gráfosztályokon gyorsabbak fejlesztése, a futásidők összevetése. A téma szoros kapcsolatban áll a leemelések elméletével.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Előfeltételek

  • C++ programozási nyelv ismerete
  • gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
  • angol nyelvismeret
Last modified 15 years ago Last modified on 11/23/09 17:26:29