4 citations · 13 across the 11 of their papers we have counts for
5 papers · 1 filter
Dense Graph Partitioning on sparse and dense graphs
Cristina Bazgan, Katrin Casel, Pierre Cazals
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of t…
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel +1
We study the problem of counting the number of homomorphisms from an input graph to a fixed (quantum) graph in any finite field of prime order . The sub…
Extension of vertex cover and independent set in some classes of graphs and generalizations
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
We consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph and a vertex set , it is asked if there exis…
On the Complexity of Solution Extension of Optimization Problems
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating min…
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a…