5 papers
A Separator-based Algorithm for the Graph Edit Distance Problem
Laura Bülte, Philip Mayer, Lars Müller +1
The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The consid…
Optimality-Preserving Data Reduction for Maximum k-Cut (Full Version)
Michael Kaibel, Petra Mutzel
Preprocessing has become an increasingly important part of solving Maximum Cut to optimality, enabling exact solvers to tackle significantly larger instances. This suggests that ex…
Bicriteria Polygon Aggregation with Arbitrary Shapes
Lotte Blank, David Eppstein, Jan-Henrik Haunert +6
We study the problem of aggregating a set of polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Equivalently, this can b…
Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
Franziska Heeg, Jonas Sauer, Petra Mutzel +1
An important characteristic of temporal graphs is how the directed arrow of time influences their causal topology, i.e., which nodes can possibly influence each other causally via…
A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
Arne Beines, Michael Kaibel, Philip Mayer +2
We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective i…