Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: induced matching

Sortuj według:

Ogranicz wyniki do:

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

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.

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

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.

On maximum induced matching numbers of special grids

Adefokun T. C., Ajayi D. O.

Journal of Mathematics and Applications

2018

Vol. 41

5--18

A subset M of the edge set of a graph G is an induced matching of G if given any two edges e1; e2 ∈ M, none of the vertices on e1 is adjacent to any of the vertices on e2. Suppose that Max(G), a positive integer, denotes the maximum size of M in G, then, M is the maximum induced matching of G and Max(G) is the maximum induced matching number of G. In this work, we obtain upper bounds for the maximum induced matching number of grid G = G n,m; n ≥ 9; m ≡ 3 mod 4; m ≥ 7, and nm odd.