Wyszukiwarka
Filtry
wszystkich: 6
Wyniki wyszukiwania dla: NP ZUPEŁNOŚĆ
-
Dominowanie w grafach
PublikacjaW pracy rozważanych jest pięć liczb dominowania: klasyczna liczba dominowania, liczba dominowania spójnego, liczba dominowania słabo spójnego, liczba dominowania słabo wypukłego i liczba dominowania wypukłego. Rozważane są pewne ograniczenia na liczby dominowania, równości między poszczególnymi liczbami, wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania i NP-zupełność problemów dominowania.
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublikacjaW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
Service restoration in survivable networks under attacks
PublikacjaW artykule dokonano porównania jakości odtwarzania usług w przeżywalnych sieciach optycznych, uszkadzanych w wyniku awarii fizycznych oraz na skutek ataków. Przeanalizowano wariant ochrony ścieżek ('path protection') poprzez wyznaczane zawczasu ścieżki zabezpieczające. Z uwagi na NP-zupełność problemu optymalizacji doboru tras w przeżywalnych sieciach optycznych, zaproponowano efektywny algorytm heurystyczny SCNDP. Autorski symulator...
-
Fast service restoration under shared protection at lightpath level in survivable WDM mesh grooming networks
PublikacjaW artykule zaproponowano nowe podejście do optymalizacji rozdziału zasobów w przeżywalnych sieciach optycznych z agregacją strumieni ruchu. Zaproponowana metoda bazuje na wierzchołkowym kolorowaniu grafu konfliktów. Jest pierwszym podejściem, dedykowanym sieciom optycznym z agregację strumieni ruchu z pełną zdolnością do konwersji długości fal, która nie powoduje wydłużenia ściezek zabezpieczjących, a więc zapewnia szybkie odtwarzanie...
-
A Tabu Search Algorithm for Optimization of Survivable Overlay Computing Systems
PublikacjaParadygmat obliczeń rozproszonych ostatnio zyskuje coraz większą uwagę, ponieważ zarówno instytucje przemysłowe, jak i uczelnie wymagają coraz większej mocy obliczeniowej do przetwarzania i analizy danych. Z uwagi na dużą podatność systemów obliczeń na awarie różnych typów (podobnie do systemów sieciowych), gwarancje przeżywalności niniejszych systemów są nieodzowne w celu zapewnienia nieprzerwanego działania usług. Z tego powodu,...
-
Rearrangeability in multicast Clos networks is NP-complete
PublikacjaPrzestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...