Max-coloring paths: tight bounds and extensions

DOI10.1007/s10878-010-9290-1zbMath1254.90272MaRDI 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 algorithm; lower bound; weighted graph; coloring

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Related Items

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

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