Parameterized complexity and approximation issues for the colorful components problems

DOI10.1016/j.tcs.2018.04.044zbMath1394.68175arXiv1605.03071OpenAlexW4235340597MaRDI QIDQ1643155

Florian Sikora, Riccardo Dondi

Publication date: 18 June 2018

Published in: Theoretical Computer Science, Pursuit of the Universal (Search for Journal in Brave)

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

zbMATH Keywords

algorithmscomputational biologyparameterized complexitycolorful components

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Parameterized complexity and approximation issues for the colorful components problems ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Finding a Small Number of Colourful Components

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Finding approximate and constrained motifs in graphs
• Multicut in trees viewed through the eyes of vertex cover
• Complexity issues in vertex-colored graph pattern matching
• Solving MAX-\(r\)-SAT above a tight lower bound
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Algorithmic and hardness results for the colorful components problems
• On the hardness of approximating minimum vertex cover
• Improved parameterized and exact algorithms for cut problems on trees
• Parameterized complexity and approximation issues for the colorful components problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Partitioning into Colorful Components by Minimum Edge Deletions
• New Races in Parameterized Algorithmics
• Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem
• OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Color-coding

This page was built for publication: Parameterized complexity and approximation issues for the colorful components problems