Ruling out FPT algorithms for weighted coloring on forests
DOI10.1016/j.tcs.2018.03.013zbMath1391.68045arXiv1703.09726OpenAlexW2794087913MaRDI QIDQ5916046
Ignasi Sau, Julien Baste, Julio Araujo
Publication date: 17 May 2018
Published in: Electronic Notes in Discrete Mathematics, Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.09726
parameterized complexityforestsweighted coloring\(\mathsf{W}[1\)-hardness]max-coloring\(\mathsf{W[1}\)-hardness]
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- A coloring problem for weighted graphs
- Fundamentals of parameterized complexity
- Max-coloring paths: tight bounds and extensions
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Strong computational lower bounds via parameterized complexity
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- Which problems have strongly exponential complexity?
- Complexity of Grundy coloring and its variants
- Approximating interval coloring and max-coloring in chordal graphs
- Reducibility among Combinatorial Problems
- Weighted Coloring in Trees
- Parameterized Algorithms
- Ruling out FPT algorithms for weighted coloring on forests
This page was built for publication: Ruling out FPT algorithms for weighted coloring on forests
