Max-coloring paths: tight bounds and extensions

DOI10.1007/S10878-010-9290-1zbMath1254.90272OpenAlexW2004394201MaRDI QIDQ454245

Julián Mestre, Telikepalli Kavitha

Publication date: 1 October 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9290-1

zbMATH Keywords

approximation algorithmlower boundweighted graphcoloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (8)

On Monte Carlo tree search for weighted vertex coloring ⋮ Iterated local search with tabu search for the weighted vertex coloring problem ⋮ Bounded max-colorings of graphs ⋮ Dual parameterization of Weighted Coloring ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ Dual parameterization of weighted coloring

Cites Work

• Unnamed Item
• A coloring problem for weighted graphs
• A class of algorithms which require nonlinear time to maintain disjoint sets
• On the max coloring problem
• Weighted coloring: further complexity and approximability results
• A linear-time algorithm for a special case of disjoint set union
• Batch Coloring Flat Graphs and Thin
• Efficiency of a Good But Not Linear Set Union Algorithm
• Automata, Languages and Programming

This page was built for publication: Max-coloring paths: tight bounds and extensions