Max-coloring and online coloring with bandwidths on interval graphs
From MaRDI portal
Publication:3189018
DOI10.1145/1978782.1978790zbMath1295.68137OpenAlexW1972620016MaRDI 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
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) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items
On the complexity of injective colorings and its generalizations, A new lower bound for the on-line coloring of intervals with bandwidth, Capacitated max-batching with interval graph compatibilities, First-Fit is linear on posets excluding two long incomparable chains, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, Clique clustering yields a PTAS for max-coloring interval graphs, Selfish Routing and Path Coloring in All-Optical Networks
