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 2016 · cs.DSShow all

7 papers · 2 filters

cs.DS2016

On the Optimality of Pseudo-polynomial Algorithms for Integer Programming

Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan +1

In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given $m \times n$ matrix $A$ and an $m$ -vector $b = (b_{1}, \dots, b_{m})$ , there is a non-nega…

cs.DS2016★ 2 cited

Bidimensionality and Kernels

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh +1

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor…

cs.DS2016

Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering

Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx +3

We prove the following theorem. Given a planar graph $G$ and an integer $k$ , it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following…

cs.DS2016★ 2 cited

Lossy Kernelization

Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan +1

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexit…

cs.DS2016

Vertex Cover Structural Parameterization Revisited

Fedor V. Fomin, Torstein J. F. Strømme

A pseudoforest is a graph whose connected components have at most one cycle. Let X be a pseudoforest modulator of graph G, i. e. a vertex subset of G such that G-X is a pseudofores…

cs.DS2016

Tight Lower Bounds on Graph Embedding Problems

Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph $G$ to graph $H$ cannot be done in time $∣ V (H) ∣^{o (∣ V (G) ∣)}$ . We al…

cs.DS2016★ 2 cited

Metric Dimension of Bounded Tree-length Graphs

Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach +1

The notion of resolving sets in a graph was introduced by Slater (1975) and Harary and Melter (1976) as a way of uniquely identifying every vertex in a graph. A set of vertices in…