Parameterized and exact algorithms for class domination coloring

DOI10.1016/j.dam.2020.12.015OpenAlexW4246450827MaRDI QIDQ2659082

R. Krithika, Saket Saurabh, Ashutosh Rai, 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

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)

Related Items

Dominator coloring and CD coloring in almost cluster graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Fundamentals of parameterized complexity
• Exact algorithms for dominating set
• Dominator colorings in some classes of graphs
• Improved upper bounds for vertex cover
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Parameterized approximation of dominating set problems
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• The maximum k-colorable subgraph problem for chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• A note on the complexity of the chromatic number problem
• The complexity of generalized clique covering
• Parameterized complexity of vertex colouring
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Algorithmic graph theory and perfect graphs
• On the complexity of cd-coloring of graphs
• Dominated colorings of graphs
• Parametrized complexity theory.
• Fast multiplication of large numbers
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The cd-Coloring of Graphs
• A Lower Bound of the cd-Chromatic Number and Its Complexity
• Set Partitioning via Inclusion-Exclusion
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Faster Parameterized Algorithms Using Linear Programming
• B-chromatic number: Beyond NP-hardness
• Parameterized Algorithms
• On dominated coloring of graphs and some Nordhaus–Gaddum-type relations

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