Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2023
On the Approximability of External-Influence-Driven Problems
Panagiotis Aivasiliotis, Aris Pagourtzis
Domination problems in general can capture situations in which some entities have an effect on other entities (and sometimes on themselves). The usual goal is to select a minimum n…