Dual parameterization of weighted coloring
From MaRDI portal
Publication:786042
DOI10.1007/s00453-020-00686-7zbMath1452.68129arXiv1805.06699OpenAlexW3081356430MaRDI QIDQ786042
Publication date: 12 August 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.06699
split graphsinterval graphsparameterized complexitypolynomial kernelsFPT algorithmsdual parameterizationmax coloringweighted coloring
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A coloring problem for weighted graphs
- Fundamentals of parameterized complexity
- Max-coloring paths: tight bounds and extensions
- Exact exponential algorithms.
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Some consequences of non-uniform conditions on uniform classes
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- On problems without polynomial kernels
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Weighted coloring: further complexity and approximability results
- A note on the complexity of the chromatic number problem
- Approximation results for the minimum graph coloring problem
- Maximizing the number of unused colors in the vertex coloring problem
- Which problems have strongly exponential complexity?
- Normal Helly circular-arc graphs and its subclasses
- On the Grundy and \(b\)-chromatic numbers of a graph
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- Dual parameterization and parameterized approximability of subset graph problems
- Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results
- Approximating interval coloring and max-coloring in chordal graphs
- Set Partitioning via Inclusion-Exclusion
- Approximating k-set cover and complementary graph coloring
- Kernelization Lower Bounds Through Colors and IDs
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- Weighted Coloring in Trees
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- A Characterization of Comparability Graphs and of Interval Graphs
- Partially Polynomial Kernels for Set Cover and Test Cover
- Ruling out FPT algorithms for weighted coloring on forests
- On the complexity of \(k\)-SAT
This page was built for publication: Dual parameterization of weighted coloring
