Preprint / Submitted

Allen Ibiapina, Raul Lopes, Andrea Marino annd Ana Silva, "Menger Theorem for Temporal Paths (Not Walks)", arxiv.

Published

Rémy Belmonte, Ararat Harutyunyan, Noleen Köhler, Nikolaos Melissinos,
"Odd Chromatic Number of Graph Classes", arxiv.
To appear in the proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023).

Chien-Chung Huang and Justin Ward,
"FPT-Algorithms for the l-Matchoid Problem with a Coverage Objective", arxiv.
To appear in SIAM Journal on Discrete Mathematics (SIDMA).

Michael Lampis, "First Order Logic on Pathwidth Revisited Again", arxiv.
To appear in the proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming, Track B (ICALP 2023).

Isnard Lopes Costa, Raul Lopes, Andrea Marino and Ana Silva, "On Computing Large Temporal (Unilateral) Connected Components", arxiv.
In the proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023).

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström,
"Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints", arxiv
In the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).

Celina M. H. de Figueiredo, Raul Lopes, Alexsander A. de Melo and Ana Silva,
"Parameterized Algorithms for Steiner Tree and Dominating Set: Bounding the Leafage by the Vertex Leafage", link.
In the prooceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM 2022).

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes and Stéphan Thomassé, "Twin-width VIII: delineation and win-wins". arxiv
In the International Symposium on Parameterized and Exact Computation (IPEC 2022).

Chien-Chung Huang and François Sellier, "Maximum Weight b-Matchings in Random-Order Streams", arxiv.
In the proceedings of the European Symposium on Algorithms (ESA 2022).

Tesshu Hanaka and Michael Lampis, "Hedonic Games and Treewidth Revisited", arxiv.
In the proceedings of the European Symposium on Algorithms (ESA 2022).

Chien-Chung Huang, François Sellier,
"Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms",
In the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). online

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström, "Directed flow-augmentation",
In the 54th Annual ACM Symposium on Theory of Computing (STOC 2022). arxiv

Mamadou Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum,
"Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k".
In the proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2022). arXiv

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, "Twin-width VI: the lens of contraction sequences".
In the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022). arXiv.

Michael Lampis and Valia Mitsou, "Fine-grained Meta-Theorems for Vertex Integrity".
In the proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021). arXiv.

Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum and Daniël Paulusma,
"Tree pivot-minors and linear rank-width", In SIAM Journal on Discrete Mathematics 35(4), p.2922-2945 (2021). arxiv.

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigan,
"Twin-width and polynomial kernels", In the proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2021). arxiv.

Jisu Jeong, Eun Jung Kim, Sang-il Oum,
"Finding branch-decompositions of matroids, hypergraphs, and more", In SIAM Journal on Discrete Mathematics, 2021. Preliminary version in ICALP 2018. arxiv.

Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos,
"A Constant-factor Approximation for Weighted Bond Cover", In the proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2021) arxiv.

Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari and Nicolas Trotignon,
"On the tree-width of even-hole-free graphs", European Journal of Combinatorics (2021) arXiv.

Michael Lampis, "Minimum Stable Cut and Treewidth", arxiv. In the Proceedings of International Colloquium on Automata, Languages and Programming (ICALP 2021).

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
"Twin-width III: Max Independent Set and Coloring", arXiv.
In the Proceedings of International Colloquium on Automata, Languages and Programming (ICALP 2021).

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos,
"Digraph Coloring and Distance to Acyclicity", In the Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), arXiv.

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigan,
"Twin-width II: small classes", In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv. The journal version appears in Combinatorial Theory, 2022.

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
"Solving hard cut problems via flow-augmentation", In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arxiv.

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
"Twin-width I: tractable FO model checking", In the Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), arxiv. The journal version appears in Journal of ACM.

Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos,
"A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth", In the Proceedings of the 28th European Symposium on Algorithms (ESA 2020), arxiv.

Chien-Chung Huang, Theophile Thiery and Justin Ward,
"Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints", In the Proceedings of International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2020), arxiv.

Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou and Yota Otachi,
"Grundy Distinguishes Treewidth from Pathwidth", In the Proceeding of the 28th European Symposium on Algorithms (ESA 2020), arxiv.
The journal version appeared in SIAM Journal on Discrete Mathematics 36 (3), 2022.

Jungho Ahn, Eun Jung Kim and Euiwoong Lee,
"Towards constant-factor approximation for chordal / distance-hereditary vertex deletion", In the Proceedings of 31st International Symposium on Algorithms and Computation (ISAAC 2020), arxiv.
The journal version appears in Algorithmica.