10.9k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University of LiverpoolGB1.9k papers
- The Ohio State UniversityUS1.9k papers
- Heidelberg UniversityDE1.9k papers
- Lawrence Berkeley National LaboratoryUS1.9k papers
- Centre National de la Recherche ScientifiqueFR1.9k papers
- University of BirminghamGB1.9k papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR1.8k papers
- National Institute for Subatomic PhysicsNL1.8k papers
- Institut National de Physique Nucléaire et de Physique des ParticulesFR1.8k papers
- Istituto Nazionale di Fisica Nucleare, Laboratori Nazionali di FrascatiIT1.8k papers
- Sapienza University of RomeIT1.8k papers
- Yale UniversityUS1.7k papers
18 papers · 2 filters
Largest chordal and interval subgraphs faster than 2^n
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk +1
We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time for some . These are the first…
Editing to a Graph of Given Degrees
Petr A. Golovach
We consider the Editing to a Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function δ:V(G)->{1,...,d}, whether it is possible to obtain a…
Minimum Bisection is fixed parameter tractable
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk +2
In the classic Minimum Bisection problem we are given as input a graph and an integer . The task is to determine whether there is a partition of into two parts an…
Parameterized Algorithms for Finding Square Roots
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach +2
We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n-1+k…
Large induced subgraphs via triangulations and CMSO
Fedor Fomin, Ioan Todinca, Yngve Villanger
We obtain an algorithmic meta-theorem for the following optimization problem. Let ϕ be a Counting Monadic Second Order Logic (CMSO) formula and t be an integer. For a given graph G…
Exploring Subexponential Parameterized Complexity of Completion Problems
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk +1
Let be a family of graphs. In the -Completion problem, we are given a graph and an integer as input, and asked whether at most edges can be added t…
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Dániel Marx, Michał Pilipczuk
Given two graphs and , the Subgraph Isomorphism problem asks if is isomorphic to a subgraph of . While NP-hard in general, algorithms exist for various parameterized…
Editing to a Connected Graph of Given Degrees
Petr A. Golovach
The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider th…
Computing Tree-depth Faster Than
Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk
A connected graph has tree-depth at most if it is a subgraph of the closure of a rooted tree whose height is at most . We give an algorithm which for a given -vertex grap…
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski +1
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is…
TREEWIDTH and PATHWIDTH parameterized by vertex cover
Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca +1
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized prob…
Long Circuits and Large Euler Subgraphs
Fedor V. Fomin, Petr A. Golovach
An undirected graph is Eulerian if it is connected and all its vertices are of even degree. Similarly, a directed graph is Eulerian, if for each vertex its in-degree is equal to it…
On the parameterized complexity of cutting a few vertices from a graph
Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen
We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph and integers , , the task is…
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach
Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012] introduced the Anchored k-Core problem, where the task is for a given graph G and integers b, k, and p to find an i…
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +1
We give two algorithms computing representative families of linear and uniform matroids and demonstrate how to use representative families for designing single-exponential paramete…
Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
Fedor V. Fomin, Michał Pilipczuk
Cutwidth of a digraph is a width measure introduced by Chudnovsky, Fradkin, and Seymour [4] in connection with development of a structural theory for tournaments, or more generally…
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Hajo Broersma, Jiří Fiala, Petr A. Golovach +3
Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval gr…
Connecting Terminals and 2-Disjoint Connected Subgraphs
Jan Arne Telle, Yngve Villanger
Given a graph and a set of terminal vertices we say that a superset of is -connecting if induces a connected graph, and is minimal if no strict sub…