10 papers
Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney
Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the co…
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn Mc Inerney +1
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per con…
Crossing Number is NP-hard for Constant Path-width (and Tree-width)
Petr Hliněný, Liana Khazaliya
The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem,…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
The -Planar Edge Completion Problem is Fixed-Parameter Tractable
Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta +2
The problem of deciding whether a biconnected planar digraph can be augmented to become an -planar graph by adding a set of oriented edges i…
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth…