On-line coloring of geometric intersection graphs
type: Item
instance of: scholarly article
title: On-line coloring of geometric intersection graphs
zbMATH Open document ID: 1008.05053
DOI: 10.1016/S0925-7721(02)00089-5
published in: Computational Geometry
publication date: 2003-03-10T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1879159
zbMATH Keywords: coloring
zbMATH Keywords: competitive analysis
zbMATH Keywords: intersection graphs
zbMATH Keywords: disk graphs
zbMATH Keywords: first-fit
zbMATH Keywords: on-line algorithm
zbMATH Keywords: square graphs
author: Thomas Erlebach
author: Jiří Fiala
MaRDI profile type: Publication
cites work: Unit disk graph recognition is NP-hard
cites work: Unit disk graphs
cites work: Polynomial-time approximation schemes for geometric graphs
cites work: Q4796709
cites work: On-line and first fit colorings of graphs
cites work: Representing graphs by disks and balls (a survey of recognition-complexity results)
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Coloring inductive graphs on-line
cites work: Q5767542
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Simple heuristics for unit disk graphs
cites work: Robust algorithms for restricted domains
cites work: Coin graphs, polyhedra, and conformal mapping
description: scientific article; zbMATH DE number 1879159