Repository logo

Browsing by Subject "maximal matching"

Filter results by typing the first few letters
Now showing 1 - 3 of 3
  • thumbnail.journal.alt
    Item type:Thesis, Access status: Restricted ,
    Skojarzenia maksymalne w strukturach grafowych
    (Data obrony: 2016-10-24) Ubysz, Aleksandra
    Wydział Matematyki Stosowanej
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    The hardness of the independence and matching clutter of a graph
    (2016) Ambarcumân, Sasun; Mkrtčân, Vahan V.; Musoân, Vahe L.; Sargsân, Hovhannes
    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 $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.
  • thumbnail.journal.alt
    Item type:Thesis, Access status: Restricted ,
    Zliczanie zbiorów niezależnych w specjalnych grafach
    (Data obrony: 2011-07-14) Stępak, Monika
    Wydział Matematyki Stosowanej