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

DOI10.1137/16M1107462zbMATH Open1393.68064MaRDI QIDQ5745127FDOQ5745127

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

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

• Title not available (Why is that?)
• Exact exponential algorithms.
• Parametrized complexity theory.
• Color-coding
• Extremal Combinatorics
• 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 (2)

• Saving colors and max coloring: some fixed-parameter tractability results
• Colored hypergraph isomorphism is fixed parameter tractable

Recommendations

• Conflict-Free Colourings of Graphs and Hypergraphs 👍 👎
• Complexity of conflict-free colorings of graphs 👍 👎
• On variants of conflict-free-coloring for hypergraphs 👍 👎
• Parameterized algorithms for conflict-free colorings of graphs 👍 👎
• Parameterized complexity of conflict-free graph coloring 👍 👎
• Parameterized Complexity of Conflict-Free Graph Coloring 👍 👎
• Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs 👍 👎
• Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs 👍 👎
• Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs 👍 👎
• A hybrid approach for exact coloring of massive graphs 👍 👎

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)