Now showing items 1-6 of 6

• #### Bisection of Bounded Treewidth Graphs by Convolutions ﻿

(Journal article; Peer reviewed, 2019)
In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint ...
• #### Complexity of the Steiner Network Problem with Respect to the Number of Terminals ﻿

(Journal article; Peer reviewed, 2019)
In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ...
• #### A Polynomial Kernel for Line Graph Deletion ﻿

(Journal article; Peer reviewed, 2020)
The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some ...
• #### A Polynomial Kernel for Paw-Free Editing ﻿

(Journal article; Peer reviewed, 2020)
For a fixed graph H, the H-free Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is ...
• #### Towards a Polynomial Kernel for Directed Feedback Vertex Set ﻿

(Journal article; Peer reviewed, 2020)
In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...
• #### A Unifying Framework for Characterizing and Computing Width Measures ﻿

(Journal article; Peer reviewed, 2022)
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, ...