TY  - JOUR
ID  - Hambardzumyan2016
LB  - Hambardzumyan2016
AU  - Hambardzumyan, Sasun
AU  - Mkrtchyan, Vahan V.
AU  - Musoyan, Vahe L.
AU  - Sargsyan, Hovhannes
TI  - The hardness of the independence and matching clutter of a graph
ST  - The hardness of the independence and matching clutter of a graph
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2016
VL  - 36
IS  - 3
SP  - 375
EP  - 397
DO  - http://dx.doi.org/10.7494/OpMath.2016.36.3.375
UR  - http://dx.doi.org/10.7494/OpMath.2016.36.3.375
AB  - 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 \(s_e\) of an edge \(e\) of a clutter is called recognizing for \(e\), if \(s_e\) 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.
KW  - clutter
KW  - hardness
KW  - independent set
KW  - maximal independent set
KW  - matching
KW  - maximal matching
SN  - 1232-9274
ER  -