Browsing Faculty of Mathematics and Natural Sciences by Journals "Algorithmica"
Now showing items 17 of 7

A FixedParameter Perspective on #BIS
(Peer reviewed; Journal article, 20190718)The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. It is believed that #BIS ... 
MimWidth II. The Feedback Vertex Set Problem
(Peer reviewed; Journal article, 2020)We give a first polynomialtime algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mimwidth). Explicitly, given a branch decomposition of mimwidth w, we give an nO(w)time ... 
On cutwidth parameterized by vertex cover
(Peer reviewed; Journal article, 201404)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... 
Parameterized complexity of Eulerian deletion problems
(Peer reviewed; Journal article, 201401)We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ... 
Parameterized complexity of the spanning tree congestion problem
(Peer reviewed; Journal article, 201209)We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apexminorfree graphs, a general class ... 
Solving the 2disjoint connected subgraphs problem faster than 2ⁿ
(Peer reviewed; Journal article, 201410)The 2DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected ... 
Subgraph Complementation
(Journal article; Peer reviewed, 202002)A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ...