Showing 2021Show all
3 papers · 1 filter
cs.DS2021
Algorithms and data structures for first-order logic with connectivity under vertex failures
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz +2
We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in…
cs.LO2021
Ordered graphs of bounded twin-width
Pierre Simon, Szymon Toruńczyk
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular…
math.CO2021
Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +3
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a…