Repository logo

Browsing by Subject "central spanning tree problem"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    Algorytm poszukiwania z zabronieniami dla problemu centralnego drzewa rozpinającego
    (Wydawnictwa AGH, 2011) Makuchowski, Mariusz
    W pracy analizuje się problem znajdowania centralnego drzewa rozpinającego. Problem ten polega na znalezieniu takiego drzewa rozpinającego graf, aby największa odległość od wszystkich pozostałych drzew była możliwie najmniejsza. Odległość pomiędzy drzewami jest miarą zliczającą różnice w zbiorze krawędzi porównywanych drzew. Zagadnienie to należy do klasy problemów NP-trudnych. W pracy proponuje się algorytm, oparty na metodzie poszukiwania z zabronieniami, dedykowany rozpatrywanemu problemowi. Praca zawiera także wyniki eksperymentów numerycznych testujących efektywność proponowanego algorytmu oraz porównuje go z algorytmem dokładnym opartym na metodzie podziału i ograniczeń.