Paloma T. Lima

IT University of Copenhagen

IT University of Copenhagen

Journal and conference versions are grouped together. If you would like to see separate lists for journal and conference publications, check dblp.

- Tree decompositions meet induced matchings: beyond Max Weight Independent Set

with M. Milanič, P. Muršič, K. Okrasa, P. Rzążewski and K. Štorgel

ESA 2024 | arXiv

- Odd Cycle Transversal on P_5-free graphs in polynomial time

with A. Agrawal, D. Lokshtanov, P. Rzążewski, S. Saurabh and R. Sharma

SODA 2024 (quasi-poly algo) | arXiv

- Structural Parameterizations of b-Coloring

with L. Jaffke and R. Sharma

ISAAC 2023 | preliminary arXiv version

- Treewidth is NP-complete on cubic graphs (and related results)

with H. Bodlaender, E. Bonnet, L. Jaffke, D. Knop, M. Milanič, S. Ordyniak, S. Pandey and O. Suchý

IPEC 2023 | arXiv

- Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset:
twin-width meets flow-augmentation

with M. Hatzel, L. Jaffke, T. Masařík, Ma. Pilipczuk, R. Sharma and M. Sorge

SODA 2023 | HALG 2023 | arXiv - A tight quasi-polynomial bound for Global Label Min-Cut

with L. Jaffke, T. Masařík, Ma. Pilipczuk and U. Souza

SODA 2023 | arXiv - b-coloring parameterized by clique-width

with L. Jaffke and D. Lokshtanov

Theory of Computing Systems (2023) Special Issue: STACS | STACS 2021 | arXiv - Reducing the vertex cover number via edge contractions

with V. F. dos Santos, I. Sau, U. Souza and P. Tale

Journal of Computer and System Sciences (2023) | MFCS 2022 | arXiv

- On the maximum number of edges in planar graphs of bounded degree and matching number

with L. Jaffke

Discrete Mathematics (2023) | arXiv

- Using edge contractions to decrease the semitotal domination number

with E. Galby, F. Mann and B. Ries

Theoretical Computer Science (2023) - On the complexity of rainbow vertex colouring diametral path graphs

with J. Dyrseth

ISAAC 2022 - XNLP-completeness for parameterized problems on graphs with a linear structure

with H. L. Bodlaender, C. Groenland, H. Jacob and L. Jaffke

IPEC 2022 Best paper award | arXiv

- Taming graphs with no large creatures and skinny ladders

with J. Gajarský, L. Jaffke, J. Novotná, Ma. Pilipczuk, P. Rzążewski and U. Souza

ESA 2022 | arXiv - Well-partitioned chordal graphs

with J. Ahn, L. Jaffke and O. Kwon

Discrete Mathematics (2022) | WG 2020 | CIAC 2021 | arXiv - Graph square roots of small distance from degree one graphs

with P. A. Golovach and C. Papadopoulos

Theory of Computing Systems (2022) | pdf | LATIN 2020 - On the maximum number of edges in chordal graphs of bounded degree and matching number

with J. R. S. Blair, P. Heggernes and D. Lokshtanov

Algorithmica (2022) Special Issue: LATIN | pdf | LATIN 2020 - Structural parameterizations of clique coloring

with L. Jaffke and G. Philip

Algorithmica (2022) | MFCS 2020 - Algorithms for the rainbow vertex coloring problem on graph classes

with E. J. van Leeuwen and M. van der Wegen

Theoretical Computer Science (2021) | MFCS 2020 - Reducing graph transversals via edge contractions

with V. F. dos Santos, I. Sau and U. S. Souza

Journal of Computer and System Sciences (2021) | pdf | MFCS 2020 | PC Newsletter - Reducing the domination number of graphs via edge contractions and vertex deletions

with E. Galby and B. Ries

Discrete Mathematics (2021) | MFCS 2019 | ISAAC 2019 - Finding connected secluded subgraphs

with P. A. Golovach, P. Heggernes and P. Montealegre

Journal of Computer and System Sciences (2020) | pdf | IPEC 2017 - Parameterized aspects of strong subgraph closure

with P. A. Golovach, P. Heggernes, A. L. Konstantinidis and C. Papadopoulos

Algorithmica (2020) | pdf | SWAT 2018 - A complexity dichotomy for critical values of the b-chromatic number of graphs

with L. Jaffke

Theoretical Computer Science (2020) | MFCS 2019 - Intersection of longest paths in graph classes

with M. R. Cerioli

Discrete Applied Mathematics (2020) | CTW 2016 - Transversals of longest paths

with M. R. Cerioli, C. G. Fernandes, R. Gómez and J. Gutiérrez

Discrete Mathematics (2020) | pdf | LAGOS 2017 - Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

with P. A. Golovach, P. Heggernes, D. Kratsch and D. Paulusma

Algorithmica (2019) | pdf | WG 2017 - Classifying k-edge colouring for H-free graphs

with E. Galby, D. Paulusma and B. Ries

Information Processing Letters (2019) | pdf - Rainbow vertex coloring bipartite graphs and chordal graphs

with P. Heggernes, D. Issac, J. Lauri and E. J. van Leeuwen

MFCS 2018

Preprints

Unpublished notes

- On the parameterized complexity of k-edge colouring
(arXiv)

with E. Galby, D. Paulusma and B. Ries