Blar i Department of Informatics på emneord "VDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422"
Viser treff 1-5 av 5
-
On cutwidth parameterized by vertex cover
(Peer reviewed; Journal article, 2014-04)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, 2014-01)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, 2012-09)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 apex-minor-free graphs, a general class ... -
Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ
(Peer reviewed; Journal article, 2014-10)The 2-DISJOINT 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 ... -
Subexponential-time parameterized algorithm for Steiner tree on planar graphs
(Peer reviewed; Journal article, 2013)The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus ...