The Linearity of First-Fit Coloring of Interval Graphs
From MaRDI portal
Publication:3815536
DOI10.1137/0401048zbMath0664.68067OpenAlexW1987042917MaRDI QIDQ3815536
Publication date: 1988
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0401048
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (43)
A graph coloring approach to the deployment scheduling and unit assignment problem ⋮ A coloring problem for weighted graphs ⋮ On the performance of the first-fit coloring algorithm on permutation graphs ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Coloring interval graphs with First-Fit ⋮ Online promise problems with online width metrics ⋮ An Improved Upper Bound for the Ring Loading Problem ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line coloring of perfect graphs ⋮ An on-line graph coloring algorithm with sublinear performance ratio ⋮ Optimizing bandwidth allocation in elastic optical networks with application to scheduling ⋮ On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ First-fit chromatic numbers of \(d\)-degenerate graphs ⋮ On-line routing in all-optical networks ⋮ First-Fit is linear on posets excluding two long incomparable chains ⋮ A note on first-fit coloring of interval graphs ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ A polynomial time approximation algorithm for dynamic storage allocation ⋮ On spectrum assignment in elastic optical tree-networks ⋮ Inequalities for the Grundy chromatic number of graphs ⋮ First-fit coloring on interval graphs has performance ratio at least 5 ⋮ Online interval coloring with packing constraints ⋮ The online graph bandwidth problem ⋮ An easy subexponential bound for online chain partitioning ⋮ On the max coloring problem ⋮ First-fit coloring of bounded tolerance graphs ⋮ Dynamic storage allocation with known durations ⋮ The greedy algorithm is optimal for on-line edge coloring ⋮ Unnamed Item ⋮ A note on the online first-fit algorithm for coloring \(k\)-inductive graphs ⋮ Online Conflict-Free Colouring for Hypergraphs ⋮ An approximation result for a periodic allocation problem ⋮ On the Max Coloring Problem ⋮ Variable sized online interval coloring with bandwidth ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Single and multiple device DSA problems, complexities and online algorithms ⋮ On-line chain partitions of orders: a survey ⋮ Unnamed Item ⋮ Bounded families for the on-line \(t\)-relaxed coloring ⋮ Coloring inductive graphs on-line ⋮ On the mean chromatic number
This page was built for publication: The Linearity of First-Fit Coloring of Interval Graphs
