Temat: completeness - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: NP-completeness of weakly convex and convex dominating set decision problems
Autorzy:: Raczek, J.
Powiązania:: https://bibliotekanauki.pl/articles/2050778.pdf
Data publikacji:: 2004
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: dominating set
NP-completeness
distance
convex set
Opis:: The convex domination number and the weakly convex domination number are new domination parameters. In this paper we show that the decision problems of convex and weakly convex dominating sets are NP-complete for bipartite and split graphs. Using a modified version of Warshall algorithm we can verify in polynomial time whether a given subset of vertices of a graph is convex or weakly convex.
Źródło:: Opuscula Mathematica; 2004, 24, 2; 189-196
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: A note on hardness of multiprocessor scheduling with scheduling solution space tree
Autorzy:: Dwibedy, Debasis
Mohanty, Rakesh
Powiązania:: https://bibliotekanauki.pl/articles/27312879.pdf
Data publikacji:: 2023
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: combinatorial structures
computational complexity
hardness
makespan
multiprocessor scheduling
multiuser
NP-completeness
nondeterministic algorithms
reduction
scheduling solution space tree
Opis:: We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
Źródło:: Computer Science; 2023, 24 (1); 53--74
1508-2806
2300-7036
Pojawia się w:: Computer Science
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "completeness" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język