Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA

Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA

  • Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym

    Publikacja

    - 2006

    W pracy rozważano złożoność obliczeniową problemu szeregowania w cylindrycznym systemie przepływowym. Skonstruowano algorytm wielomianowy dla problemu dwumaszynowego oraz wykazano, iż zagadnienie staje się NP-trudne przy szeregowaniu na trzech procesorach, bądź na dwóch, przy dodatkowym wymuszeniu braku obustronnych przestojów.

  • The complexity of list ranking of trees

    Publikacja

    Uporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...

    Pełny tekst w serwisie zewnętrznym

  • On the complexity of distributed greedy coloring

    Publikacja

    - 2007

    W pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.

    Pełny tekst w serwisie zewnętrznym

  • Złożoność obliczeniowa

    Kursy Online

  • Joanna Raczek dr inż.

    Wykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i Telekomunikacji,...

  • Jerzy Konorski dr hab. inż.

    Jerzy Konorski otrzymał tytuł mgr inż. telekomunikacji na Poitechnice Gdańskiej, zaś stopień doktora n.t. w dyscyplinie informatyka w Instytucie Podstaw Informatyki PAN. W r. 2007 obronił rozprawę habilitacyjną na Wydziale Elektroniki, Telekomnikacji i Informatyki PG. Jest autorem ponad 150 publikacji naukowych, prowadził projekty naukowo-badawcze finansowane ze środków Komitetu Badań Naukowych, UE, US Air Force Office of Scientific...

  • T-coloring of graphs.

    Publikacja

    - 2004

    Niniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.

  • The circular chromatic index of some class 2 graphs

    Publikacja

    W artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.

    Pełny tekst w serwisie zewnętrznym

  • Kolorowanie grafów obciążonych i jego zastosowanie w problemie przydziału częstotliwości

    Publikacja

    Referat omawia jeden z modeli dla problemu przydziału częstotliwości, oparty o kolorowanie grafów obciążonych. Podana została złożoność obliczeniowa modelu i wielomianowy algorytm 4-kolorowania grafów w tym modelu.

  • Cykliczny system otwarty i cyrkularne kolorowanie grafów.

    Publikacja

    - 2002

    W pracy rozważany jest cykliczny system otwarty - modyfikacja otwartego systemu procesów dedykowanych polegająca na założeniu, że praca jest wykonywana w ruchu ciągłym, czyli kolejne cykle pracy wykonywane są bezpośrednio po sobie. Rozważana jest złożoność obliczeniowa problemów związanych z układaniem harmonogramu w systemach tego typu.

  • Fast Distance Vector Field Extraction for Facial Feature Detection

    Publikacja

    Praca dotyczy metody lokalizowania cech twarzy z wykorzystaniem wektorowych pól odległości (DVF), zaproponowanej przez Asteriadisa. Zawiera skrótowy opis tej koncepcji oraz prezentuje ulepszenia wprowadzone przez autorów do oryginalnego rozwiązania. Główną zaletą wprowadzonych zmian jest znacznie zredukowana złożoność obliczeniowa algorytmu, jak również zwiększona precyzja wektorowego pola odległości wyznaczanego w wyniku jego...

  • Determining the optimal course alteration maneouvre in a multi-target encounter situation for a given ship domain model

    W artykulee przedstawiono nową deterministyczną metodę wyznaczania niezbędnego manewru kursem dla sytuacji spotkania z wieloma obiektami obcymi i dla dowolnej zadanej domeny. Jej prostota i niska złożoność obliczeniowa czynią ją dobrą alternatywą dla obecnie stosowanych metod. Główny algorytm został przedstawiony wprost, tak aby mógł być bezpośrednio zastosowany w pokładowych systemach antykolizyjnych lub w systemach VTS.

  • Metoda szybkiego wyznaczania par węzłowo rozłącznych tras dla ochrony transmisji unicast

    W celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże, złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. W pracy prezentujemy nowe podejście wyznaczania par rozłącznych tras bazujące na transformacji grafu sieci w meta strukturę. Wyniki badań odnośnie czasu wyznaczania tras...

    Pełny tekst w serwisie zewnętrznym

  • Numerical Algorithms of Planning Safe Ship Trajectories for ARPA Systems

    Publikacja

    Głównym celem pracy było zaprojektowanie metody znajdowania bezpiecznych trajektorii statków, która byłaby prosta w implementacji, szybka (niska złożoność obliczeniowa)i deterministyczna, elastyczna (umożliwiałaby zastosowanie dowolnej domeny). Aby zrealizować cel należało zbadać bieżący stan wiedzy w dziedzinie,zaprojektować nową metodę, zaimplementować metodę (wraz ze wszystkimi niezbędnymi algorytmami) w środowisku programistycznym...

  • Analiza tolerancji filtrów Gm-C czasu ciągłego.

    Publikacja

    W pracy przedstawiono efektywną metodę analizy tolerancji dla dowolnych filtrów Gm-C. Korzystając z ogólnego modelu filtrów tej klasy oraz jego opisu macierzowego wyprowadzono formuły pozwalające na wyznaczanie zniekształceń charakterystyk częstotliwościowych filtrów spowodowanych rozrzutem rzeczywistych wartości elementów filtru względem wartości nominalnych. Złożoność obliczeniowa związana z ewaluacją tych formuł jest...

  • Wielkogabarytowe hydrodynamiczne łożyska wzdłużne

    Publikacja

    - 2012

    W monografii przedstawiono problemy konstrukcyjne i badawcze hydrodynamicznych łożysk wzdłużnych o dużych średnicach. Łożyska takie stanowią istotne i niezwykle odpowiedzialne podzespoły hydrogeneratorów elektrowni wodnych. Z uwagi na rozmiary (średnice przekraczają niekiedy 5 metrów) i złożoność zjawisk łożyska te wymagają specjalnej postaci konstrukcyjnej, a ich dokładna analiza obliczeniowa przysparza wiele problemów. Dodatkowo...

  • Metoda analizy związanych z czasem wymagań dotyczących bezpieczeństwa systemów komputerowych

    Publikacja

    Bezpieczeństwo jest pożądaną cecha systemów przemysłowych, transportowych i innych typów. A ponieważ do sterowania tymi systemami powszechnie stosuje się systemy komputerowe, jest ono również ważną cechą oprogramowania. Analiza bezpieczeństwa oprogramowania jest jednak, ze względu na jego niematerialność, trudniejsza od typowej analizy. Ponadto, ze względu na skomplikowane reguły sterujące oraz naturę kontrolowanych systemów, bezpieczeństwo...

    Pełny tekst w portalu

  • Piotr Borowiecki dr hab. inż.

  • Zero-visibility cops and robber and the pathwidth of a graph

    Publikacja

    - JOURNAL OF COMBINATORIAL OPTIMIZATION - 2015

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...

    Pełny tekst w serwisie zewnętrznym

  • The Complexity of Zero-Visibility Cops and Robber

    Publikacja

    - 2014

    In this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.

    Pełny tekst w serwisie zewnętrznym

  • Parallel processing subsystems with redundancy in a distributed environment

    Publikacja

    W pracy rozważano problem podziału systemu rozproszonego na spójne podsystemy złożone z przynajmniej trzech jednostek, pozwalające na detekcję i skorygowanie pojedynczych błędów. Wykazano, że problem maksymalizacji liczby takich jednostek jest NP-trudny nawet dla dwuspójnych kubicznych topologii sieci. Podano też nowe algorytmy przybliżone.

    Pełny tekst w serwisie zewnętrznym

  • Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.

    Rozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.

    Pełny tekst w serwisie zewnętrznym

  • Efficient list cost coloring of vertices and/or edges of some sparse graphs

    Publikacja

    Rozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.

  • Paired domination and doubly domination in graphs

    Publikacja

    - 2007

    W rozprawie poruszane są zagadnienia związane z dominowaniem parami w grafach oraz domiowaniem totalno - powściągniętym w grafach. Ponadto omawiane są zagadnienia związane ze złożonością obliczeniową różnych problemów dominowania w grafach.

  • The maximum edge-disjoint paths problem in complete graphs

    Rozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...

    Pełny tekst w serwisie zewnętrznym

  • Forwarding and optical indices of a graph

    W pracy rozstrzygnięto dwa problemy dotyczące komunikacji wszyscy-do-wszystkich w grafach. Stwierdzono, że dla wersji skierowanej problemu parametry ''pi'' (maksymalne obciążenie krawędzi) i ''w'' (parametr chromatyczny) nie muszą być w ogólności sobie równe. Dla wersji nieskierowanej problemu pokazano, że wyznaczenie wartości zarówno ''pi'', jak i ''w'', jest w ogólności problemem NP-trudnym.

    Pełny tekst w serwisie zewnętrznym

  • Cost minimization in wireless networks with a bounded and unbounded number of interfaces

    Publikacja

    - NETWORKS - 2009

    Praca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne. Rozważono zarówno wariant, w którym liczba interfejsów komunikacyjnych jest parametrem stałym (narzuconym...

    Pełny tekst w serwisie zewnętrznym

  • Inferring perfect phylogenies with restrictions on character state transitions

    Publikacja

    Znana z klasycznej literatury metoda rekonstrukcji drzewa filogenetycznego zbioru gatunków na podstawie ich cech analizowanych w modelu doskonałej filogenezy często okazuje się niewystarczająca ze względu na założenia tego modelu, zmuszające do pominięcia znanych biologom informacji. W pracy definiujemy rozszerzenie umożliwiając wprowadzenie dla każdej cechy grafu skierowanego dopuszczalnych przejść ewolucyjnych pomiędzy jej stanami....

  • Cost minimisation in unbounded multi-interface networks

    Publikacja

    - 2008

    W pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...

    Pełny tekst w serwisie zewnętrznym

  • The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree

    W pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny...

    Pełny tekst w serwisie zewnętrznym

  • Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

    Publikacja

    - 2008

    W pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.

    Pełny tekst w serwisie zewnętrznym

  • Some results on trading model in a consensus list coloring

    Publikacja

    Konsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...

  • Two-Rate Based Low-Complexity Variable Fractional-Delay FIR Filter Structures

    This paper considers two-rate based structures for variable fractional-delay (VFD) finite-length impulse response (FIR) filters. They are single-rate structures but derived through a two-rate approach. The basic structure considered hitherto utilizes a regular half-band (HB) linear-phase filter and the Farrow structure with linear-phase subfilters. Especially for wide-band specifications, this structure is computationally efficient...

    Pełny tekst w serwisie zewnętrznym

  • Connected searching of weighted trees

    W pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.

    Pełny tekst w serwisie zewnętrznym

  • An efficient algorithm for finding ideal schedules

    Publikacja

    - ACTA INFORMATICA - 2012

    Podejmujemy problem szeregowania zadań jednostkowych z zadanymi czasamy przybycia i zależnościami kolejnościowymi. Uszeregowanie jest idealne jeśli jednocześnie minimalizuje maksymalny oraz średni czas zakończenia zadania. Podajemy przyklad pokazujący, że uszeregowania idealne nie istnieją dla relacji zależności zadań będącej drzewem, gdy dopuścimy możliwość wystąpienia przerwań. Z drugiej strony podajemy algorytm o złożoności...

    Pełny tekst w serwisie zewnętrznym

  • Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths

    Publikacja

    - WIRELESS NETWORKS - 2009

    Rozważano zagadnienie minimalizacji energii w sieciach bezprzewodowych bez infrastruktury, w których niektóre węzły są wyposażone w więcej, niż jeden interfejs. W przyjętym modelu sieci podano nowe algorytmy przybliżone oraz wyniki dotyczące złożoności obliczeniowej dla dwóch problemów: aktywacji najtańszej spójnej podsieci spinającej oraz aktywacji ścieżki pomiędzy ustaloną parą węzłów.

    Pełny tekst w serwisie zewnętrznym

  • Mixed graph edge coloring

    Publikacja

    - DISCRETE MATHEMATICS - 2009

    W pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.

    Pełny tekst w serwisie zewnętrznym

  • A note on the strength and minimum color sum of bipartite graphs

    Siłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.

    Pełny tekst w serwisie zewnętrznym

  • Connectivity in Multi-Interface Networks

    Publikacja

    - 2009

    Rozważano zagadnienie minimalizacji energii w sieciach bezprzewodowych bez infrastruktury, w których niektóre węzły są wyposażone w więcej, niż jeden interfejs. W przyjętym modelu sieci podano nowe algorytmy przybliżone oraz wyniki dotyczące złożoności obliczeniowej dla problemu najtańszej spójnej podsieci spinającej.

    Pełny tekst w serwisie zewnętrznym

  • What Can Be Observed Locally? Round based models for quantum distributed computing

    Publikacja

    - 2009

    W pracy rozważono zagadnienie lokalności w kontekście informacji kwantowej w obliczeniach rozproszonych. Rozważono dwa kwantowe rozszerzenia modelu LOCAL Liniala, otrzymane poprzez: (1) inicjalizację systemu w kwantowym stanie splątanym, (2) zastosowanie kwantowych kanałów komunikacyjnych. Dla obydwu typów rozszerzeń zaproponowano przykłady problemów, których złożoność rundowa ulega redukcji w porównaniu do oryginalnego modelu...

    Pełny tekst w serwisie zewnętrznym

  • The complexity of minimum-length path decompositions

    Publikacja

    We consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...

    Pełny tekst w serwisie zewnętrznym

  • The complexity of zero-visibility cops and robber

    Publikacja

    - THEORETICAL COMPUTER SCIENCE - 2015

    We consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...

    Pełny tekst w serwisie zewnętrznym

  • Classical coloring of graphs.

    Publikacja

    Rozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.

  • Chromatyczne szeregowanie zadań w cyklicznych systemach produkcyjnych.

    Publikacja

    - 2005

    Głównym celem pracy jest klasyfikacja złożoności obliczeniowej problemu szeregowania zadań w przypadku cyklicznej pracy systemu produkcyjnego. Rozważane są przy tym trzy modele szeregowania: system zadań dwuprocesorowych, system otwarty i system przepływowy. Kryterium optymalizacyjnym które jest analizowane jest długość cyklu wyrażająca częstość realizacji poszczególnych zestawów operacji. W pracy posługiwano się teorią grafów...

  • Cykliczny system otwarty z ograniczeniami obustronnych przestojów

    Publikacja

    - 2005

    W pracy badany jest system otwarty, który pracuje cyklicznie, tj. po ukończeniu jednego zestawu zadań przetwarzany jest kolejny zestaw identycznych zadań. Narzucone jest przy tym ograniczenie polegające na braku przestojów zarówno po stronie procesów jak i zadań. Wykazana jest NP-trudność problemu konstrukcji uszeregowania spełniającego te założenia jak i problemu minimalizacji długość i cyklu.

  • Szeregowanie zadań sprzężonych metodą kolorowania grafów

    Rozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.

  • Metoda chromatyczna i jej zastosowania techniczne

    Artykuł ma charakter przeglądowy. Przedstawiono w nim najważniejsze modele koloryzowania grafów i ich zastosowania w wybranych problemach technicznych. Ponieważ jest to wiodąca tematyka badawcza Katedry Podstaw Informatyki Wydziału ETI Politechniki Gdańskiej, praca służy również upowszechnianiu dorobku naukowego pracowników Katedry oraz osób z nią współpracujących w opisywanej dziedzinie.

  • Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych

    Niniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów wszeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.

  • Szeregowanie zadań metodami kolorowania grafów.Monografie 37.

    Publikacja

    - 2003

    Niniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.

  • NP-completeness of convex and weakly convex domiating set decision problems.

    Publikacja

    Liczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.

    Pełny tekst w portalu