Wyniki wyszukiwania - BazTech

1

Time-free Solution to Independent Set Problem using P Systems with Active Membranes

Nguyen Viet Dung, Pham Ba Thai, Phan Thuan Do

Fundamenta Informaticae

|

2021

|

Vol. 182, nr 3

243--255

EN

Membrane computing is a branch of natural computing aiming to abstract computing models from the structure and functioning of living cells. The computation models obtained in the field of membrane computing are usually called P systems. P systems have been used to solve computationally hard problems efficiently on the assumption that the execution of each rule is completed in exactly one time-unit (a global clock is assumed for timing and synchronizing the execution of rules). However, in biological reality, different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, with this biological reality, we give a time-free solution to independent set problem using P systems with active membranes, which solve the problem independent of the execution time of the involved rules.

2

Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Nguyen Viet Dung, Pham Ba Thai, Do Phan Thuan

Fundamenta Informaticae

|

2021

|

Vol. 182, nr 3

257--283

EN

We first design an (n2) solution for finding a maximum induced matching in permutation graphs given their permutation models, based on a dynamic programming algorithm with the aid of the sweep line technique. With the support of the disjoint-set data structure, we improve the complexity to (m+n). Consequently, we extend this result to give an (m+n) algorithm for the same problem in trapezoid graphs. By combining our algorithms with the current best graph identification algorithms, we can solve the MIM problem in permutation and trapezoid graphs in linear and (n2) time, respectively. Our results are far better than the best known (mn) algorithm for the maximum induced matching problem in both graph classes, which was proposed by Habib et al.

3

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

Furmańczyk H., Kubale M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2003

|

T. 7, z. 1-2

97-104

PL

W pracy rozważyliśmy problem szeregowania zadań sprzężonych na pojedynczym procesorze. Zadanie nazywamy sprzężonym (coupled task), jeżeli składa się z dwóch operacji oraz przerwy pomiędzy nimi, czyli druga z operacji może być wykonana dopiero po ściśle określonym czasie od zakończenia wykonywania operacji pierwszej. Pomiędzy zadaniami określona jest relacja kolejności ich wykonywania. Mamy dwa rodzaje ograniczeń kolejnościowych - silne i słabe. W pracy tej rozważyliśmy model, w którym czas wykonywania każdej operacji jest ten sam, równy 1, oraz długość przerwy jest stała dla wszystkich zadań. Ograniczenia kolejnościowe przyjęliśmy jako silne, a kryterium minimalizacyjnym jest łączny czas wykonywania zadań. Z takim zagadnieniem spotykamy się w systemach sterowania urządzeniami radarowymi, gdzie pierwsza operacja odpowiada wysłaniu sygnału, natomiast druga odebraniu jego echa. W przypadku ogólnym problem szeregowania zadań sprzężonych jest NP-trudny. Rozważyliśmy przypadki, gdy ograniczenia kolejnościowe definiują częściowy porządek na zadaniach oraz odpowiadający graf ma postać grafu permutacyjnego, kografu, grafu dwudzielnego lub drzewa, czyli uogólniając - grafu porównywalnego. W niektórych przypadkach rozważany problem można rozwiązać w czasie wielomianowym. Odpowiednie uszeregowanie uzyskaliśmy wykorzystując modele kolorowania grafów - ograniczonego i sprawiedliwego.

EN

In this paper we have considered a problem of coupled task scheduling on one processor. A task is called coupled if it contains two operations and a gap between them, so that the second operation has to be processed some time after a completion of the first one. There are defined precedence constraints between processing tasks. We have got two kinds of precedence constraints: strict and weak. In this work we have considered the model where tasks are identical with processing time of operations equal to 1 and the length of the gap being constant and the same for all tasks. The precedence constraints are strict and the optimization criterion is to minimize the schedule length. This problem often appears in radar-like devices, where the first operation is the transmission of a pulse and the second is the reception of its echo. In general, the problem of coupled task scheduling is NP-hard. We have considered cases where precedence constraints define partial order on task set and the associated graph is a permutation graph, cograph, bipartite graph or tree, so generally a comparability graph. In some cases our problem is shown to be solvable in polynomial time. We obtain schedules of coupled tasks using appropriate models of graph coloring - bounded and equitable.