Publications

Showing 35 publications

2025

Awesome graph parameters

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

2025•

DOI arXiv

Computing Tree Decompositions with Small Independence Number

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

2025•ACM Transactions on Algorithms

DOI arXiv

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

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

2025•

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

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

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

2025•

DOI arXiv

Sufficient Conditions for Polynomial-Time Detection of Induced Minors.

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

2025•Theory and Practice of Computer Science(SOFSEM)

DOI arXiv

2024

Finding k-community structures in special graph classes.

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

2024•Discrete Applied Mathematics

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•International Workshop on Combinatorial Algorithms(IWOCA)

DOI

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

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

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

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

Conditions for minimally tough graphs

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

2023•

arXiv

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

2021

Colourful components in k-caterpillars and planar graphs.

Janka Chlebíková and Clément Dallard

2021•Theoretical Computer Science

DOI arXiv

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(LATIN)

DOI

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•7th International Conference on Algorithmic Decision Theory(ADT)

DOI

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

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•International Workshop on Combinatorial Algorithms(IWOCA)

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•International Workshop on 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•International Workshop on Combinatorial Algorithms(IWOCA)

DOI

Complexity of Scheduling for DARP with Soft Ride Times.

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

2019•International Conference on 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•International Conference on Combinatorial Optimization and Applications(COCOA)

DOI

Publications

2025

Awesome graph parameters

Computing Tree Decompositions with Small Independence Number

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

Layered tree-independence number and clique-based separators.

On constrained intersection representations of graphs and digraphs.

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

Induced Minor Models. I. Structural Properties and Algorithmic Consequences

Sufficient Conditions for Polynomial-Time Detection of Induced Minors.

2024

Finding k-community structures in special graph classes.

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

Graphs with at most two moplexes.

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

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

Functionality of box intersection graphs

Treewidth versus clique number. II. Tree-independence number.

2023

Conditions for minimally tough graphs

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.

2021

Colourful components in k-caterpillars and planar graphs.

Graphs with Two Moplexes.

Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs.

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

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

Vertex Cover at Distance on H-Free Graphs.

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