University of Bergen

output

19932026

most citedObservation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC

10.9k citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing 2014 · cs.DSShow all

12 papers · 2 filters

cs.DS2014★ 2 cited

A Polynomial Kernel for Trivially Perfect Editing

Pål Grønås Drange, Michał Pilipczuk

We give a kernel with $O (k^{7})$ vertices for Trivially Perfect Editing, the problem of adding or removing at most $k$ edges in order to make a given graph trivially perfect. This an…

cs.DS2014

Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter

Sigve Hortemo Sæther

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more g…

cs.DS2014★ 2 cited

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

Ariel Gabizon, Daniel Lokshtanov, Michal Pilipczuk

In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation"…

cs.DS2014

Parameterized Complexity of Bandwidth on Trees

Markus Sortland Dregi, Daniel Lokshtanov

The bandwidth of a $n$ -vertex graph $G$ is the smallest integer $b$ such that there exists a bijective function $f : V (G) \to {1, ..., n}$ , called a layout of $G$ , such tha…

cs.DS2014

Between Treewidth and Clique-width

Sigve Hortemo Sæther, Jan Arne Telle

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be…

cs.DS2014

On the Ordered List Subgraph Embedding Problems

Olawale Hassan, Iyad Kanj, Daniel Lokshtanov +1

In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs $G$ and $H$ , each with a linear order defined on its vertices, a function $L$ that a…

cs.DS2014

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,..…

cs.DS2014

On the Computational Complexity of Vertex Integrity and Component Order Connectivity

Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof

The Weighted Vertex Integrity (wVI) problem takes as input an $n$ -vertex graph $G$ , a weight function $w : V (G) \to N$ , and an integer $p$ . The task is to decide if there exis…

cs.DS2014★ 2 cited

Solving MaxSAT and #SAT on structured CNF formulas

Sigve Hortemo Sæther, Jan Arne Telle, Martin Vatshelle

In this paper we propose a structural parameter of CNF formulas and use it to identify instances of weighted MaxSAT and #SAT that can be solved in polynomial time. Given a CNF form…

cs.DS2014

Representative Sets of Product Families

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +1

A subfamily $F^{'}$ of a set family $F$ is said to $q$ -{\em represent} $F$ if for every $A \in F$ and $B$ of size $q$ such that $A \cap B = \emptyset$ ther…

cs.DS2014

A subexponential parameterized algorithm for Proper Interval Completion

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk +1

In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a gr…

cs.DS2014★ 2 cited

A subexponential parameterized algorithm for Interval Completion

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk +1

In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting…