- Tytuł:
- The hardness of the independence and matching clutter of a graph
- Autorzy:
-
Hambardzumyan, S.
Mkrtchyan, V. V.
Musoyan, V. L.
Sargsyan, H. - Powiązania:
- https://bibliotekanauki.pl/articles/952814.pdf
- Data publikacji:
- 2016
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
clutter
hardness
independent set
maximal independent set
matching
maximal matching - Opis:
- 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.
- Źródło:
-
Opuscula Mathematica; 2016, 36, 3; 375-397
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł