Obstructions and Recognition of Graphs with Linear Rankwidth 1

Prelegent(ci)

Andrzej Proskurowski

Afiliacja

University of Oregon, Eugene

Termin

30 maja 2014 14:15

Pokój

p. 5820

Seminarium

Research Seminar of the Logic Group: Approximate reasoning in data mining

---

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.

---