6 citations · 27 across the 25 of their papers we have counts for
6 papers · 1 filter
The Hierarchy of Saturating Matching Numbers
Hans U. Simon, Jan Arne Telle
In this paper, we study three matching problems all of which came up quite recently in the field of machine teaching. The cost of a matching is defined in such a way that, for some…
On a Combinatorial Problem Arising in Machine Teaching
Brigt Håvardstun, Jan Kratochvíl, Joakim Sunde +1
We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minim…
Classes of intersection digraphs with good algorithmic properties
Lars Jaffke, O-joung Kwon, Jan Arne Telle
An intersection digraph is a digraph where every vertex is represented by an ordered pair of sets such that there is an edge from to if and only if a…
The graph formulation of the union-closed sets conjecture
Henning Bruhn, Pierre Charbit, Oliver Schaudt +1
In 1979 Frankl conjectured that in a finite non-trivial union-closed collection of sets there has to be an element that belongs to at least half the sets. We show that this is equi…
On the boolean-width of a graph: structure and applications
Y. Rabinovich, J. A. Telle
We study the recently introduced boolean-width of graphs. Our structural results are as follows. Firstly, we show that almost surely the boolean-width of a random graph on vert…
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
David R. Wood, Jan Arne Telle
Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrar…