Leírás
Legyen G=(V, E) hurokélmentes gráf, melynek kijelöljük a pontjainak egy T
részhalmazát. A T-beli pontokat temináloknak nevezzük. A továbbiakban
T-útnak fogjuk nevezni G minden útját, melyre teljesül, hogy a két
végpontja T-ben van, és minden belső pontja T-n kívül. A feladatunk, hogy
találjunk G-ben maximálisan sok éldiszjunkt T-utat.
Az előadásban bemutatásra kerül egy kombinatorikus, determinisztikus
algoritmus a maximálisan sok éldiszjunkt T-út meghatározásához. Az eljárás
során egy címkézett segédgráfot használunk arra, hogy az eddig talált
éldiszjunkt T-utak számát növeljük. A növeléshez egy megfelelő sétából
indulunk ki, amelynek meghatározásához egy olyan algoritmust használunk, amely
analóg Edmonds kehely algoritmusával, annak azonban nem specializálása, és nem
általánosítása.
Az eljárásról azt is be fogjuk látni, hogy ha nem tudja tovább növelni a
T-utak számát, akkor megtalálta a maximumot. Végül meg fogjuk határozni az
algoritmus bonyolultságát is, azaz belátjuk, hogy futásideje csupán
O(|V||E|^2), ami sokkal gyorsabb, mint az eddig talált legjobb
determinisztikus
algoritmus.
----------------------------------------------------------------
Az előadás NEM valós idejű streamen lesz közvetítve, hanem egy videóra adunk
linket, melyen hangalámondásos diák vannak. (A videó hossza csak 82 perc.)
Viszont az előadótól az előadás ideje alatt lehet emailben kérdezni a
bogigal95 at gmail...
email címen.