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

DOI10.1137/16M1107462MaRDI QIDQ5745127zbMATH OpenFDO

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)

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)

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

Cites work

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

Cited in

(4)

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

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)