Browsing Bergen Open Research Archive by Author "Eiben, Eduard"
Now showing items 15 of 5

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. ...