Parameterized and exact algorithms for class domination coloring
type: Item
instance of: scholarly article
title: Parameterized and exact algorithms for class domination coloring
author: R. Krithika
author: Ashutosh Rai
author: Saket Saurabh
author: Prafullkumar Tale
published in: Discrete Applied Mathematics
publication date: 2021-03-25T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 68Rxx
zbMATH DE Number: 7327719
zbMATH Keywords: class domination coloring
zbMATH Keywords: fixed parameter tractable
zbMATH Keywords: exact algorithm
zbMATH Keywords: NP hardness
zbMATH Keywords: chordal and split graphs
MaRDI profile type: Publication
full work available at URL: j.dam.2020.12.015
OpenAlex ID: W4246450827
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: Set Partitioning via Inclusion-Exclusion
cites work: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
cites work: Parameterized complexity of vertex colouring
cites work: Dominator colorings in some classes of graphs
cites work: Improved upper bounds for vertex cover
cites work: On dominated coloring of graphs and some Nordhaus–Gaddum-type relations
cites work: The complexity of generalized clique covering
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: Parameterized Algorithms
cites work: Q3374865
cites work: Fundamentals of parameterized complexity
cites work: Parameterized approximation of dominating set problems
cites work: Parametrized complexity theory.
cites work: Q4198056
cites work: Exponential time algorithms for the minimum dominating set problem on some graph classes
cites work: Q5403013
cites work: Q3429518
cites work: Algorithmic graph theory and perfect graphs
cites work: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
cites work: A note on the complexity of the chromatic number problem
cites work: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Faster Parameterized Algorithms Using Linear Programming
cites work: Q3558598
cites work: Dominated colorings of graphs
cites work: Q5710169
cites work: B-chromatic number: Beyond NP-hardness
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: Exact algorithms for dominating set
cites work: Fast multiplication of large numbers
cites work: The cd-Coloring of Graphs
cites work: A Lower Bound of the cd-Chromatic Number and Its Complexity
cites work: On the complexity of cd-coloring of graphs
cites work: Color class domination number of middle graph and center graph of \(K_{1,n}\), \(C_n\) and \(P_n\)
cites work: The maximum k-colorable subgraph problem for chordal graphs
DOI: 10.1016/J.DAM.2020.12.015
Recommended article: Parameterized and Exact Algorithms for Class Domination Coloring
Recommended article: Algorithmic Aspects of Dominator Colorings in Graphs
Recommended article: Exact and Parameterized Algorithms for (k, i)-Coloring
Recommended article: Exact and approximative algorithms for coloring G(n,p)
Recommended article: Parameterized algorithms for conflict-free colorings of graphs
Recommended article: Q3424889
Recommended article: An exact algorithm for the partition coloring problem
Recommended article: Complexity of total dominator coloring in graphs
Recommended article: Dominating set based exact algorithms for \(3\)-coloring
description: scientific article