Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Opuscula Mathematica

1 2016

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: maximal matching

Sortuj według:

Ogranicz wyniki do:

The hardness of the independence and matching clutter of a graph

Hambardzumyan S., Mkrtchyan V. V., Musoyan V. L., Sargsyan H.

Opuscula Mathematica

2016

Vol. 36, no. 3

375--397

A clutter (or antichain or Sperner family) L is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.