52 citations · 150 across the 20 of their papers we have counts for
23 papers
Chimaera: A Mixture-of-Graph-Experts Architecture for Cross-Task and Cross-Dataset Graph Learning
Jonathan Frank, David Richerby, Ansgar Scherp
Designing foundation models for graphs is challenging due to the irregular structure of graphs and the different sizes and characteristics of embeddings. Chimaera integrates mixtur…
A Framework for Reputation Aware Uninorm-driven Consensus Algorithms for Blockchain Networks
Bruno Ramos-Cruz, Javier Andreu-Perez, David Richerby +1
The operation of blockchain is governed by consensus algorithms (CA). Several consensus mechanisms require significant computational power, while others necessitate high amounts of…
Lifelong Graph Learning for Graph Summarization
Jonatan Frank, Marcel Hoffmann, Nicolas Lell +2
Summarizing web graphs is challenging due to the heterogeneity of the modeled information and its changes over time. We investigate the use of neural networks for lifelong graph su…
Multi-View Structural Graph Summaries
Jonatan Frank, Andor Diera, David Richerby +1
A structural graph summary is a small graph representation that preserves structural information necessary for a given task. The summary is used instead of the original graph to co…
Computing -Bisimulations for Large Graphs: A Comparison and Efficiency Analysis
Jannik Rau, David Richerby, Ansgar Scherp
Summarizing graphs w.r.t. structural features is important to reduce the graph's size and make tasks like indexing, querying, and visualization feasible. Our generic parallel BRS a…
Graph Summarization with Graph Neural Networks
Maximilian Blasi, Manuel Freudenreich, Johannes Horvath +2
The goal of graph summarization is to represent large graphs in a structured and compact way. A graph summary based on equivalence classes preserves pre-defined features of a graph…
Time and Memory Efficient Parallel Algorithm for Structural Graph Summaries and two Extensions to Incremental Summarization and -Bisimulation for Long -Chaining
Till Blume, Jannik Rau, David Richerby +1
We developed a flexible parallel algorithm for graph summarization based on vertex-centric programming and parameterized message passing. The base algorithm supports infinitely man…
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
Leslie Ann Goldberg, John Lapinskas, David Richerby
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is…
Phase Transitions of the Moran Process and Algorithmic Consequences
Leslie Ann Goldberg, John Lapinskas, David Richerby
The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every…
Functional Clones and Expressibility of Partition Functions
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum +2
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions ) closed under (essentially) multiplication, summati…
Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg +2
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlyin…
Counting Homomorphisms to Square-Free Graphs, Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
We study the problem HomsTo of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph . A characteristic feature of modular counting is that ca…
Absorption Time of the Moran Process
Josep Diaz, Leslie Ann Goldberg, David Richerby +1
The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a…
The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and computer science can be…
Counting list matrix partitions of graphs
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan +2
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is c…
The complexity of approximating conservative counting CSPs
Xi Chen, Martin Dyer, Leslie Ann Goldberg +4
We study the complexity of approximately solving the weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, ther…
On the Fixation Probability of Superstars
Josep Diaz, Leslie Ann Goldberg, George B. Mertzios +3
The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness is introduced into a population and the system evolves, either rea…
Approximating Fixation Probabilities in the Generalized Moran Process
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios +3
We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected g…
The complexity of weighted and unweighted #CSP
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +3
We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our red…
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
Martin Dyer, David Richerby
Bulatov (2008) gave a dichotomy for the counting constraint satisfaction problem #CSP. A problem from #CSP is characterised by a constraint language, which is a fixed, finite set o…
The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius +1
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs wi…
The Complexity of Approximating Bounded-Degree Boolean \sharp CSP
Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius +1
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP wit…
The Complexity of Weighted Boolean #CSP with Mixed Signs
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +2
We give a complexity dichotomy for the problem of computing the partition function of a weighted Boolean constraint satisfaction problem. Such a problem is parameterized by a set o…