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

DOI10.1137/16M1107462zbMATH Open1393.68064MaRDI QIDQ5745127FDOQ5745127

Authors: Pradeesha Ashok, Aditi Dudeja, Sudeshna Kolay, Saket Saurabh 

Publication date: 5 June 2018

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

Recommendations

• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• Parameterized algorithms for conflict-free colorings of graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Conflict-free colourings of graphs and hypergraphs
• Parameterized complexity of conflict-free graph coloring
• Parameterized Complexity of Conflict-Free Graph Coloring
• On variants of conflict-free-coloring for hypergraphs
• Complexity of conflict-free colorings of graphs
• A hybrid approach for exact coloring of massive graphs

zbMATH Keywords

conflict-free coloringFPT algorithmsunique-maximum coloringmaximization algorithms

Mathematics Subject Classification ID

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

Cites Work

• Exact exponential algorithms.
• Parametrized complexity theory.
• Title not available (Why is that?)
• Color-coding
• Extremal combinatorics. With applications in computer science
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colourings of graphs and hypergraphs
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring and its applications
• Conflict-free colouring of graphs
• The parameterized complexity of unique coverage and its variants
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Graph unique-maximum and conflict-free colorings

Cited In (4)

• Saving colors and max coloring: some fixed-parameter tractability results
• Colored hypergraph isomorphism is fixed parameter tractable
• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• On conflict-free multi-coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5745127)