Parameterized and Exact Algorithms for Class Domination Coloring
DOI10.1007/978-3-319-51963-0_26zbMath1444.68147arXiv2203.09106OpenAlexW2571262586MaRDI QIDQ2971145
R. Krithika, Saket Saurabh, Ashutosh Rai, Prafullkumar Tale
Publication date: 4 April 2017
Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.09106
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (8)
Cites Work
- 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
- Fast multiplication of large numbers
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The cd-Coloring of Graphs
- 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
This page was built for publication: Parameterized and Exact Algorithms for Class Domination Coloring