Dual parameterization of Weighted Coloring
From MaRDI portal
Publication:5009474
DOI10.4230/LIPIcs.IPEC.2018.12OpenAlexW2962785990MaRDI QIDQ5009474
No author found.
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/lipics.ipec.2018.12
split graphsinterval graphsparameterized complexitypolynomial kernelsFPT algorithmsdual parameterizationmax coloringweighted coloring
Related Items (2)
A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
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
- 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?
- On the Grundy and \(b\)-chromatic numbers of a graph
- Incidence matrices and interval 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
