Obstructions to faster diameter computation: Asteroidal sets

G Ducoffe - arXiv preprint arXiv:2209.12438, 2022 - arxiv.org
An extremity is a vertex such that the removal of its closed neighbourhood does not increase
the number of connected components. Let $ Ext_ {\alpha} $ be the class of all connected …

[图书][B] Dualities in graphs and digraphs

M Hatzel - 2023 - library.oapen.org
In this thesis we describe dualities in directed as well as undirected graphs based on tools
such as width-parameters, obstructions and substructures. We mainly focus on directed …

Graphs with at most two moplexes

C Dallard, R Ganian, M Hatzel, M Krnc… - Journal of Graph …, 2024 - Wiley Online Library
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from
chordal graphs to general graphs. The notion is known to be closely related to lexicographic …