Finding a Small Number of Colourful Components

DOI10.4230/LIPIcs.CPM.2019.20OpenAlexW2955146193MaRDI QIDQ5088911

Laurent Bulteau, Konrad K. Dabrowski, Daniël Paulusma, Stéphane Vialette, Matthew Johnson, Guillaume Fertin

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1808.03561

zbMATH Keywords

treetreewidthvertex covercolourful componentcolourful partition

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (1)

Colourful components in \(k\)-caterpillars and planar graphs

Cites Work

• Algorithmic and hardness results for the colorful components problems
• Parameterized complexity and approximation issues for the colorful components problems
• On the parameterized complexity of colorful components and related problems
• Graph minors. XIII: The disjoint paths problem
• Towards a complexity dichotomy for colourful components problems on \(k\)-caterpillars and small-degree planar graphs
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Partitioning into Colorful Components by Minimum Edge Deletions
• OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Complexity of Multiterminal Cuts
• Approximation Algorithms for Some Graph Partitioning Problems
• The complexity of satisfiability problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Finding a Small Number of Colourful Components