1 citations · 1 across the 3 of their papers we have counts for
8 papers
Structural Parameterizations for Eternal Vertex Cover
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani +1
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph . To begin with, the defender places guards on vertices of . The attacker, on the…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki +1
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the pre…
Finding -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki +1
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the pre…
A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Mueller, Sebastian Ordyniak +2
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that lin…
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Hans Bodlaender, Nick Brettell, Matthew Johnson +3
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…