Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs

DOI10.1137/16M1107462zbMath1393.68064MaRDI QIDQ5745127

Sudeshna Kolay, Pradeesha Ashok, Saket Saurabh, Aditi Dudeja

Publication date: 5 June 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

conflict-free coloringFPT algorithmsunique-maximum coloringmaximization algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Complexity of conflict-free colorings of graphs
• Exact exponential algorithms.
• Graph unique-maximum and conflict-free colorings
• The parameterized complexity of unique coverage and its variants
• Conflict-free coloring of points and simple regions in the plane
• Parametrized complexity theory.
• Extremal Combinatorics
• Conflict-Free Colourings of Graphs and Hypergraphs
• Color-coding
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-Free Coloring and its Applications
• Conflict-Free Colouring of Graphs

This page was built for publication: Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs