research
∙
09/21/2023
Recognizing unit multiple intervals is hard
Multiple interval graphs are a well-known generalization of interval gra...
share
research
∙
10/28/2021
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
04/08/2021
Scaling up graph homomorphism for classification via sampling
Feature generation is an open topic of investigation in graph machine le...
research
∙
11/16/2020
The Longest Run Subsequence Problem: Further Complexity Results
Longest Run Subsequence is a problem introduced recently in the context ...
research
∙
03/23/2020
On the complexity of Broadcast Domination and Multipacking in digraphs
We study the complexity of the two dual covering and packing distance-ba...
research
∙
01/11/2020
Grundy Coloring friends, Half-Graphs, Bicliques
The first-fit coloring is a heuristic that assigns to each vertex, arriv...
research
∙
11/06/2018
Weighted Upper Edge Cover: Complexity and Approximability
Optimization problems consist of either maximizing or minimizing an obje...
research
∙
10/10/2018
Extension of vertex cover and independent set in some classes of graphs and generalizations
We consider extension variants of the classical graph problems Vertex Co...
research
∙
10/10/2018
On the Complexity of Solution Extension of Optimization Problems
The question if a given partial solution to a problem can be extended re...
research
∙
07/30/2018
Parameterized Orientable Deletion
A graph is d-orientable if its edges can be oriented so that the maximum...
research
∙
07/14/2018
Token Sliding on Split Graphs
We show that the independent set reconfiguration problem on split graphs...
research
∙
06/04/2018
Covering with Clubs: Complexity and Approximability
Finding cohesive subgraphs in a network is a well-known problem in graph...
research
∙
12/13/2017
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
10/31/2017
Designing RNA Secondary Structures is Hard
An RNA sequence is a word over an alphabet on four elements {A,C,G,U} ca...
research
∙
09/13/2017