Max-coloring and online coloring with bandwidths on interval graphs
From MaRDI portal
Publication:3189018
DOI10.1145/1978782.1978790zbMath1295.68137MaRDI QIDQ3189018
Rajiv Raman, Kasturi R. Varadarajan, Sriram V. Pemmaraju
Publication date: 9 September 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1978782.1978790
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Selfish Routing and Path Coloring in All-Optical Networks, On the complexity of injective colorings and its generalizations, First-Fit is linear on posets excluding two long incomparable chains, Clique clustering yields a PTAS for max-coloring interval graphs, Capacitated max-batching with interval graph compatibilities, A new lower bound for the on-line coloring of intervals with bandwidth, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs