research
∙
08/31/2022
On weighted graph separation problems and flow-augmentation
One of the first application of the recently introduced technique of flo...
share
research
∙
07/15/2022
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
We study the parameterized problem of satisfying “almost all” constraint...
research
∙
06/01/2022
Algorithmic Applications of Tree-Cut Width
The recently introduced graph parameter tree-cut width plays a similar r...
research
∙
04/01/2022
Twin-width VIII: delineation and win-wins
We introduce the notion of delineation. A graph class 𝒞 is said delineat...
research
∙
12/19/2021
Attacks of the Knights: Exploiting Non Uniform Cache Access Time
Intel Knights Landing Processors have shared last level cache (LLC) acro...
research
∙
11/05/2021
Directed flow-augmentation
We show a flow-augmentation algorithm in directed graphs: There exists a...
research
∙
10/30/2021
Twin-width VI: the lens of contraction sequences
A contraction sequence of a graph consists of iteratively merging two of...
research
∙
10/28/2021
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
07/06/2021
Twin-width and polynomial kernels
We study the existence of polynomial kernels, for parameterized problems...
research
∙
05/03/2021
A Constant-factor Approximation for Weighted Bond Cover
The Weighted ℱ-Vertex Deletion for a class F of graphs asks, weighted gr...
research
∙
04/28/2021
Continual Learning Approach for Improving the Data and Computation Mapping in Near-Memory Processing System
The resurgence of near-memory processing (NMP) with the advent of big da...
research
∙
09/02/2020
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which t...
research
∙
08/17/2020
Grundy Distinguishes Treewidth from Pathwidth
Structural graph parameters, such as treewidth, pathwidth, and clique-wi...
research
∙
08/12/2020
On the tree-width of even-hole-free graphs
The class of all even-hole-free graphs has unbounded tree-width, as it c...
research
∙
07/28/2020
Twin-width III: Max Independent Set and Coloring
We recently introduced the graph invariant twin-width, and showed that f...
research
∙
07/17/2020
Solving hard cut problems via flow-augmentation
We present a new technique for designing FPT algorithms for graph cut pr...
research
∙
06/17/2020
Twin-width II: small classes
The twin-width of a graph G is the minimum integer d such that G has a d...
research
∙
04/30/2020
Twin-width I: tractable FO model checking
Inspired by a width invariant defined on permutations by Guillemot and M...
research
∙
01/11/2020
Grundy Coloring friends, Half-Graphs, Bicliques
The first-fit coloring is a heuristic that assigns to each vertex, arriv...
research
∙
10/10/2019
Remote Control: A Simple Deadlock Avoidance Scheme for Modular System on Chip
The increase in design cost and complexity have motivated designers to a...
research
∙
02/13/2019
New Results on Directed Edge Dominating Set
We study a family of generalizations of Edge Dominating Set on directed ...
research
∙
11/30/2018
Spatial analysis between particulate matter and emergency room visits for conjunctivitis and keratitis
Background: The concentration of particulate matter in the air varies de...
research
∙
09/21/2018
Data-compression for Parametrized Counting Problems on Sparse graphs
We study the concept of compactor, which may be seen as a counting-analo...
research
∙
07/14/2018
Token Sliding on Split Graphs
We show that the independent set reconfiguration problem on split graphs...
research
∙
12/13/2017
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
11/04/2017
Finding branch-decompositions of matroids, hypergraphs, and more
Given n subspaces of a finite-dimensional vector space over a fixed fini...
research
∙
11/02/2017
Erdős-Pósa property of chordless cycles and its applications
A chordless cycle in a graph G is an induced subgraph of G which is a cy...
research
∙
02/25/2014
The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
We study the computational complexity of problems that arise in abstract...
research
∙
04/21/2011