Éldiszjunkt útrendszer kiterjesztése

Szabó, Jácint (2008) Éldiszjunkt útrendszer kiterjesztése. ALKALMAZOTT MATEMATIKAI LAPOK, 25. pp. 119-129. ISSN 0133-3399

Preview

Text 04ALKMAT_25.pdf - Published Version Download (1MB) | Preview

Abstract

A dolgozatban egy újfajta problématípussal, az úgynevezett kiterjesztési problémával foglalkozunk. Az off-line kiterjesztési problémában adott egy G hálózat egész élkapacitásokkal, valamint egy H\ és egy H2 igénygráf egységnyi igényekkel ugyanazon a ponthalmazon. Feladatunk meghatározni az olyan F Ç E{H\)C\E{H2) élhalmazok méretének maximumát, amelyeknek van olyan G-beli egész útkiosztása, amely kiterjeszthető H\, valamint H2 egy-egy egész G-beli útkiosztásává. Az online kiterjesztési problémában adott egy G hálózat egész élkapacitásokkal, egy Я igénygráf egy G-beli útkiosztással, valamint egy Я2 igénygráf egységnyi igényekkel, amelyre E(H) С Я(Я2 ) teljesül. Kérdés, mekkora az olyan F Ç E(H) élhalmazok méretének maximuma, amelyekre az adott útkiosztás F-re való megszorítása kiterjeszthető H2 egy egész útkiosztásává? Attól függően, hogy a gráfok irányítottak vagy irányítatlanok, négy különböző feladatot kapunk. Mind a négy NP-teljes, de e dolgozatban teljes megoldást adunk e feladatokra abban az esetben, amikor G egy gyűrű és az igénygráfok csillagok.

Actions (login required)

Edit Item