12 citations · 31 across the 16 of their papers we have counts for
16 papers
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…
Maximal induced matchings in triangle-free graphs
Manu Basavaraju, Pinar Heggernes, Pim van 't Hof +2
An induced matching in a graph is a set of edges whose endpoints induce a -regular subgraph. It is known that any -vertex graph has at most maxima…
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…
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…
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…