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
11 papers · 2 filters
A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov +1
A graph is called a \emph{block graph} if each maximal -connected component of is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective o…
Simultaneous Feedback Vertex Set: A Parameterized Perspective
Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad +1
Given a family of graphs , a graph , and a positive integer , the -Deletion problem asks whether we can delete at most vertices from to obta…
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté +3
The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this pape…
Independence and Efficient Domination on -free Graphs
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen
In the Independent set problem, the input is a graph , every vertex has a non-negative integer weight, and the task is to find a set of pairwise non-adjacent vertices, maxim…
Editing to a Planar Graph of Given Degrees
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +2
We consider the following graph modification problem. Let the input consist of a graph , a weight function , a cost function $c\colo…
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A centra…
Maximum matching width: new characterizations and a fast algorithm for dominating set
Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle
We give alternative definitions for maximum matching width, e.g. a graph has if and only if it is a subgraph of a chordal graph and for every…
Lower Bounds for the Graph Homomorphism Problem
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
The graph homomorphism problem (HOM) asks whether the vertices of a given -vertex graph can be mapped to the vertices of a given -vertex graph such that each edge of…
Uniform Kernelization Complexity of Hitting Forbidden Minors
Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov +1
The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph…
Parameterized Complexity of Superstring Problems
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach +3
In the Shortest Superstring problem we are given a set of strings and integer and the question is to decide whether there is a superstring of le…
Parameterized Complexity of Secluded Connectivity Problems
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov +1
The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a…