11 citations · 15 across the 14 of their papers we have counts for
4 papers · 1 filter
Awesome graph parameters
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin +2
For a graph , we denote by the size of a maximum independent set and by the size of a maximum clique in . Our paper lies on the edge of two lines of research, r…
Graph Classes Closed under Self-intersection
Konrad K. Dabrowski, Vadim V. Lozin, Martin Milanič +3
A graph class is monotone if it is closed under taking subgraphs. It is known that a monotone class defined by finitely many obstructions has bounded treewidth if and only if one o…
Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Andreas Göbel, Nicolas Klodt +3
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs on the same vertex set, and asks for a walk of s…
Complexity of learning matchings and half graphs via edge queries
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic ty…