Parameterized and exact algorithms for class domination coloring

DOI10.1016/J.DAM.2020.12.015OpenAlexW4246450827MaRDI QIDQ2659082FDOQ2659082

Authors: R. Krithika, Ashutosh Rai, Saket Saurabh, Prafullkumar Tale 

Publication date: 25 March 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.12.015

Recommendations

• Parameterized and exact algorithms for class domination coloring
• Algorithmic aspects of dominator colorings in graphs
• Exact and parameterized algorithms for \((k,i)\)-coloring
• Exact and approximative algorithms for coloring G(n,p)
• Parameterized algorithms for conflict-free colorings of graphs
• Efficient algorithms for parameterized \(H\)-colorings
• An exact algorithm for the partition coloring problem
• Complexity of total dominator coloring in graphs
• Dominating set based exact algorithms for \(3\)-coloring

zbMATH Keywords

exact algorithmfixed parameter tractableNP hardnesschordal and split graphsclass domination coloring

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Graph theory
• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• The node-deletion problem for hereditary properties is NP-complete
• Algorithmic graph theory and perfect graphs
• Parametrized complexity theory.
• Fast multiplication of large numbers
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized algorithms
• Title not available (Why is that?)
• Improved upper bounds for vertex cover
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• The maximum k-colorable subgraph problem for chordal graphs
• The complexity of generalized clique covering
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Set partitioning via inclusion-exclusion
• Parameterized complexity of vertex colouring
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Coloring edges and vertices of graphs without short or long cycles
• A note on the complexity of the chromatic number problem
• Faster parameterized algorithms using linear programming
• B-chromatic number: beyond NP-hardness
• Dominator colorings and safe clique partitions
• Minimum dominating set approximation in graphs of bounded arboricity
• Dominated colorings of graphs
• Parameterized approximation of dominating set problems
• Exact algorithms for dominating set
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Dominator colorings in some classes of graphs
• Exponential time algorithms for the minimum dominating set problem on some graph classes
• On the complexity of cd-coloring of graphs
• Color class domination number of middle graph and center graph of \(K_{1,n}\), \(C_n\) and \(P_n\)
• The cd-coloring of graphs
• A lower bound of the cd-chromatic number and its complexity
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• On dominated coloring of graphs and some Nordhaus–Gaddum-type relations

Cited In (7)

• Dominator coloring and CD coloring in almost cluster graphs
• On the complexity of minimum \(q\)-domination partization problems
• The cd-coloring of graphs
• A lower bound of the cd-chromatic number and its complexity
• Parameterized and exact algorithms for class domination coloring
• On CD-chromatic number and its lower bound in some classes of graphs
• Total domination, separated-cluster, CD-coloring: algorithms and hardness

This page was built for publication: Parameterized and exact algorithms for class domination coloring

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