Browsing Department of Informatics by Author "Eiben, Eduard"
Now showing items 16 of 6

Bisection of Bounded Treewidth Graphs by Convolutions
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. (Journal article; Peer reviewed, 2019)In the Bisection problem, we are given as input an edgeweighted 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
Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)In the Directed Steiner Network problem we are given an arcweighted 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
Lochet, William; Eiben, Eduard (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 PawFree Editing
Eiben, Eduard; Lochet, William; Saurabh, Saket (Journal article; Peer reviewed, 2020)For a fixed graph H, the Hfree 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
Bergougnoux, Benjamin; Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian; Ramanujan, M. S. (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
Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Jaffke, Lars; Kwon, Ojoung (Journal article; Peer reviewed, 2022)Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or cliquewidth have so far traditionally been tailored to specific width parameters. Moreover, for mimwidth, ...