Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

 

Obstructions and Recognition of Graphs with Linear Rankwidth 1


Seminarium Zakładu Logiki Matematycznej

Prelegent: Andrzej Proskurowski

2014-05-30 14:15

Using a split-decomposition algorithm, we decide in linear time the membership in the class of graphs with linear rank-width at most 1 or
exhibit an induced subgraph which belongs to the set of minimal forbidden induced subgraphs for the class. From the complete set of such obstructions, we derive both the vertex-minor and pivot-minor obstructions for the class.