Parameterized algorithms for conflict-free colorings of graphs

DOI10.1016/j.tcs.2018.05.025zbMath1401.68126arXiv1710.00223OpenAlexW2963708823WikidataQ129757968 ScholiaQ129757968MaRDI QIDQ1786593

I. Vinod Reddy

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeparameterized complexityconflict-free coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Conflict-free coloring bounds on open neighborhoods ⋮ A tight bound for conflict-free coloring in terms of distance to cluster ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs

Cites Work

• Fundamentals of parameterized complexity
• A survey of the algorithmic aspects of modular decomposition
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring of unit disks
• Complement reducible graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parameterized complexity of vertex colouring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph Theory
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Deterministic conflict-free coloring for intervals
• Parameterized and Exact Computation
• Parameterized Algorithms
• Transitiv orientierbare Graphen

This page was built for publication: Parameterized algorithms for conflict-free colorings of graphs