5 citations · 10 across the 17 of their papers we have counts for
4 papers · 1 filter
Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width
Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger +1
The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the con…
Cuts and Gauges for Submodular Width
Matthias Lanzinger
Submodular width is a central structural measure governing the complexity of conjunctive query evaluation. In this paper we recast submodular width in geometric terms. We how that…
FPT Parameterisations of Fractional and Generalised Hypertree Width
Matthias Lanzinger, Igor Razgon, Daniel Unterberger
We present the first fixed-parameter tractable (FPT) algorithms for exact computation of generalized hypertree width (ghw) and fractional hypertree width (fhw). Our algorithms are…
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
Matthias Lanzinger, Igor Razgon
Generalised hypertree width () is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing of a…