Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: interval graph

Sortuj według:

Ogranicz wyniki do:

On the weightedk-path vertex cover on interval graphs

Zygadło Jakub

Schedae Informaticae

2020

Vol. 29

9--21

We consider a version of the k-path vertex cover problem that asks for the minimum weight subset C of vertices of a graph G such that every path on k vertices in G has at least one vertex in common with C. We present two dynamic algorithms solving this problem on interval graphs. The first one works on general interval graphs but is in practice limited to small values of k. The second algorithm computes minimum weight vertex cover for arbitrary k on proper interval graph G = (V,E) in time O(|V|^2|E|).

Neighbourhood of Constant Order in the Interval Graph of a Random Boolean Function

Daubner J., Toman E.

Fundamenta Informaticae

2013

Vol. 122, nr 4

275--295

In the present paper we estimate the size of a neighbourhood of constant order in the interval graph of a random Boolean function. So far, no bound of this parameter has been known.