Publications

Showing 36 publications

2026

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

Clément Dallard, Daniël Paulusma, and Erik Jan van Leeuwen

2026•

DOI arXiv

Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction

Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, and Ulrich Pferschy

2026•Networks

DOI arXiv

Induced minor models. I. Structural properties and algorithmic consequences

Nicolas Bousquet, Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, and Nicolas Trotignon

2026•Journal of Computer and System Sciences

DOI arXiv

Computing Tree Decompositions with Small Independence Number

Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič

2026•ACM Transactions on Algorithms

DOI arXiv

2025

Awesome graph parameters

Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, and Viktor Zamaraev

2025•

DOI arXiv

Minimizing maximum dissatisfaction in the allocation of indivisible items under a common preference graph

Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, and Ulrich Pferschy

2025•Discrete Optimization

DOI arXiv

Layered tree-independence number and clique-based separators

Clément Dallard, Martin Milanič, Andrea Munaro, and Shizhou Yang

2025•

DOI arXiv

On constrained intersection representations of graphs and digraphs

Ferdinando Cicalese, Clément Dallard, and Martin Milanič

2025•

DOI arXiv

Sufficient Conditions for Polynomial-Time Detection of Induced Minors

Clément Dallard, Maël Dumas, Claire Hilaire, and Anthony Perez

2025•SOFSEM 2025: Theory and Practice of Computer Science(SOFSEM)

DOI arXiv

2024

Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors

Clément Dallard, Maël Dumas, Claire Hilaire, and Anthony Perez

2024•

DOI arXiv

Finding $k$-community structures in special graph classes

Narmina Baghirova, Clément Dallard, Bernard Ries, and David Schindl

2024•Discrete Applied Mathematics

DOI arXiv

Graphs with at most two moplexes

Clément Dallard, Robert Ganian, Meike Hatzel, Matjaž Krnc, and Martin Milanič

2024•Journal of Graph Theory

DOI arXiv

Computing Tree Decompositions with Small Independence Number

Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič

2024•51st International Colloquium on Automata, Languages, and Programming(ICALP)

DOI

Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure

Clément Dallard, Martin Milanič, and Kenny Štorgel

2024•Journal of Combinatorial Theory, Series B

DOI arXiv

Detecting $K_{2,3}$ as an Induced Minor

Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, and Nicolas Trotignon

2024•Combinatorial Algorithms(IWOCA)

DOI

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

Clément Dallard, Matjaž Krnc, O-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel, and Sebastian Wiederrecht

2024•

DOI arXiv

Functionality of Box Intersection Graphs

Clément Dallard, Vadim Lozin, Martin Milanič, Kenny Štorgel, and Viktor Zamaraev

2024•Results in Mathematics

DOI arXiv

Treewidth versus clique number. II. Tree-independence number

Clément Dallard, Martin Milanič, and Kenny Štorgel

2024•Journal of Combinatorial Theory, Series B

DOI arXiv

2023

Allocation of indivisible items with individual preference graphs

Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, Ulrich Pferschy, and Nevena Pivač

2023•Discrete Applied Mathematics

DOI arXiv

Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride Problems

Janka Chlebíková, Clément Dallard, and Niklas Paulsen

2023•Theoretical Computer Science

DOI

2022

On Constrained Intersection Representations of Graphs and Digraphs

Ferdinando Cicalese, Clément Dallard, and Martin Milanič

2022•33rd International Symposium on Algorithms and Computation(ISAAC)

DOI

On minimally tough chordal graphs

Clément Dallard, Blas Fernández, Gyula Y. Katona, Martin Milanič, and Kitti Varga

2022•

DOI arXiv

2021

Colourful components in k-caterpillars and planar graphs

Janka Chlebíková and Clément Dallard

2021•Theoretical Computer Science

DOI arXiv

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Clément Dallard, Martin Milanič, and Kenny Štorgel

2021•SIAM Journal on Discrete Mathematics

DOI arXiv

Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs

Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, Nevena Pivač, and Ulrich Pferschy

2021•Algorithmic Decision Theory(ADT)

DOI

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad

2021•Algorithmica

DOI arXiv

Vertex Cover at Distance on H-Free Graphs

Clément Dallard, Mirza Krbezlija, and Martin Milanič

2021•Combinatorial Algorithms(IWOCA)

DOI

Graphs with Two Moplexes

Clément Dallard, Robert Ganian, Meike Hatzel, Matjaž Krnc, and Martin Milanič

2021•XI Latin and American Algorithms, Graphs and Optimization Symposium(LAGOS)

DOI

2020

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E Mouawad

2020•31st International Symposium on Algorithms and Computation(ISAAC)

DOI

Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure

Clément Dallard, Martin Milanič, and Kenny Štorgel

2020•Graph-Theoretic Concepts in Computer Science(WG)

DOI

Graphs without a partition into two proportionally dense subgraphs

Cristina Bazgan, Janka Chlebíková, and Clément Dallard

2020•Information Processing Letters

DOI arXiv

2019

Proportionally dense subgraph of maximum size: Complexity and approximation

Cristina Bazgan, Janka Chlebíková, Clément Dallard, and Thomas Pontoizeau

2019•Discrete Applied Mathematics

DOI arXiv

Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs

Janka Chlebíková and Clément Dallard

2019•Combinatorial Algorithms(IWOCA)

DOI

Complexity of Scheduling for DARP with Soft Ride Times

Janka Chlebíková, Clément Dallard, and Niklas Paulsen

2019•Algorithms and Complexity(CIAC)

DOI

2018

Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases

Mathias Weller, Annie Chateau, Clément Dallard, and Rodolphe Giroudeau

2018•Algorithmica

DOI

2016

Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding

Clément Dallard, Mathias Weller, Annie Chateau, and Rodolphe Giroudeau

2016•Combinatorial Optimization and Applications(COCOA)

DOI

Publications

2026

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

Allocation of Indivisible Items With a Common Preference Graph: Minimizing Total Dissatisfaction

Induced minor models. I. Structural properties and algorithmic consequences

Computing Tree Decompositions with Small Independence Number

2025

Awesome graph parameters

Minimizing maximum dissatisfaction in the allocation of indivisible items under a common preference graph

Layered tree-independence number and clique-based separators

On constrained intersection representations of graphs and digraphs

Sufficient Conditions for Polynomial-Time Detection of Induced Minors

2024

Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors

Finding $k$-community structures in special graph classes

Graphs with at most two moplexes

Computing Tree Decompositions with Small Independence Number

Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure

Detecting $K_{2,3}$ as an Induced Minor

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

Functionality of Box Intersection Graphs

Treewidth versus clique number. II. Tree-independence number

2023

Allocation of indivisible items with individual preference graphs

Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride Problems

2022

On Constrained Intersection Representations of Graphs and Digraphs

On minimally tough chordal graphs

2021

Colourful components in k-caterpillars and planar graphs

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Vertex Cover at Distance on H-Free Graphs

Graphs with Two Moplexes

2020

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure

Graphs without a partition into two proportionally dense subgraphs

2019

Proportionally dense subgraph of maximum size: Complexity and approximation

Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs

Complexity of Scheduling for DARP with Soft Ride Times

2018

Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases

2016

Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding

Co-authors