COIN-OR::LEMON - Graph Library

Version 1 (modified by Peter Kovacs, 14 years ago) (diff)

--

Tranzitív lezárt

Hatékony algoritmus implementálása egy gráf tranzitív lezártjának előállítására.

Háttér

Egy G=(V,E) irányított gráf tranzitív lezártja az a G' =(V,E' ) gráf, amelyben u-ból v-be pontosan akkor vezet él, ha u-ból vezet irányított út v-be az eredeti G gráfban.

Egy gráf tranzitív lezártja könnyen kiszámítható pl. a Floyd-Warshall-algoritmussal O(n3) időben, illetve n szélességi kereséssel O(n(n+m)) időben. Ugyanakkor vannak lényegesen hatékonyabb módszerek is, amelyek a gyakorlatban majdnem lineáris időben futnak.

Egy ilyen módszer az erősen összefüggő komponensek meghatározásán, valamint a komponensek gráfjának topologikus rendezésén alapul, de összetett adatszerkezeteket is alkalmaz. További információ: http://www.cs.hut.fi/~enu/thesis.html

Feladat

A feladat minél hatékonyabb algoritmusok implementálása, valamint a különböző módszerek összehasonlítása.

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

Kapcsolódó ticketek: #378.

Előfeltételek

  • C++ programozási nyelv ismerete
  • gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
  • angol nyelvismeret