The Linearity of First-Fit Coloring of Interval Graphs

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

scientific article; zbMATH DE number 17824
A polynomial time approximation algorithm for dynamic storage allocation
Coloring interval graphs with First-Fit
An optimal greedy heuristic to color interval graphs
First-fit coloring on interval graphs has performance ratio at least 5

Cited in

(49)

Variable sized online interval coloring with bandwidth
On-line dimension for posets excluding two long incomparable chains
Online interval coloring with packing constraints
Inequalities for the Grundy chromatic number of graphs
First-fit coloring of bounded tolerance graphs
On the on-line chromatic number of the family of on-line 3-chromatic graphs
On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
An on-line graph coloring algorithm with sublinear performance ratio
On the Max Coloring Problem
On the max coloring problem
A polynomial time approximation algorithm for dynamic storage allocation
A graph coloring approach to the deployment scheduling and unit assignment problem
On the on-line coloring of unit interval graphs with proper interval representation
First-Fit is linear on posets excluding two long incomparable chains
First-fit chromatic numbers of \(d\)-degenerate graphs
On spectrum assignment in elastic optical tree-networks
On-line chain partitions of orders: a survey
A coloring problem for weighted graphs
scientific article; zbMATH DE number 17824 (Why is no real title available?)
On the performance guarantee of first fit for sum coloring
A (2+)-approximation algorithm for the storage allocation problem
An easy subexponential bound for online chain partitioning
Online promise problems with online width metrics
On the performance of the first-fit coloring algorithm on permutation graphs
A note on the online first-fit algorithm for coloring \(k\)-inductive graphs
The online graph bandwidth problem
scientific article; zbMATH DE number 7278054 (Why is no real title available?)
On-line coloring of perfect graphs
Open problems on graph coloring for special graph classes
The greedy algorithm is optimal for on-line edge coloring
On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
Coloring inductive graphs on-line
Breaking the barrier of 2 for the storage allocation problem
Coloring interval graphs with First-Fit
On-line routing in all-optical networks
On the mean chromatic number
Single and multiple device DSA problems, complexities and online algorithms
On the \textsc{FirstFit} algorithm for online unit-interval coloring
Dynamic storage allocation with known durations
Optimizing bandwidth allocation in elastic optical networks with application to scheduling
An approximation result for a periodic allocation problem
Bounded families for the on-line \(t\)-relaxed coloring
scientific article; zbMATH DE number 820116 (Why is no real title available?)
Improved algorithms for scheduling unsplittable flows on paths
First-fit coloring on interval graphs has performance ratio at least 5
Forbidden structures for efficient first-fit chain partitioning (extended abstract)
A note on first-fit coloring of interval graphs
An improved upper bound for the ring loading problem
Online conflict-free colouring for hypergraphs

This page was built for publication: The Linearity of First-Fit Coloring of Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815536)