scientific article; zbMATH DE number 6469191

zbMath1318.68129MaRDI QIDQ5501309

Rajiv Raman, Kasturi R. Varadarajan, Sriram V. Pemmaraju

Publication date: 3 August 2015

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Iterated local search with tabu search for the weighted vertex coloring problem ⋮ On the max-weight edge coloring problem ⋮ On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ First-fit chromatic numbers of \(d\)-degenerate graphs ⋮ A Refined Analysis of Online Path Coloring in Trees ⋮ A note on the Cornaz-Jost transformation to solve the graph coloring problem ⋮ First-Fit is linear on posets excluding two long incomparable chains ⋮ Bounded max-colorings of graphs ⋮ A note on first-fit coloring of interval graphs ⋮ First-fit coloring on interval graphs has performance ratio at least 5 ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Online unit clustering: Variations on a theme ⋮ Online interval coloring with packing constraints ⋮ An easy subexponential bound for online chain partitioning ⋮ On the max coloring problem ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ First-fit coloring of bounded tolerance graphs ⋮ Minimum entropy combinatorial optimization problems ⋮ Unnamed Item ⋮ Approximating the max-edge-coloring problem ⋮ On the Maximum Edge Coloring Problem ⋮ On the Max Coloring Problem ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Complexity and online algorithms for minimum skyline coloring of intervals ⋮ Max-coloring of vertex-weighted graphs ⋮ A one-to-one correspondence between colorings and stable sets ⋮ A Dichotomy Theorem for First-Fit Chain Partitions ⋮ Minimum entropy coloring ⋮ Variable sized online interval coloring with bandwidth ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Weighted coloring: further complexity and approximability results

This page was built for publication: