A note on first-fit coloring of interval graphs

DOI10.1007/S11083-008-9076-6MaRDI QIDQ925259zbMATHOpenAlexFDO

Authors N. S. Narayanaswamy, R. Subhash Babu

Publication date 3 June 2008

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-008-9076-6

zbMATH Keywords

competitive analysiscolumn construction methodfirst fit for online graph coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Coloring interval graphs with First-Fit
• Online coloring co-interval graphs
• First-fit coloring on interval graphs has performance ratio at least 5
• The Linearity of First-Fit Coloring of Interval Graphs
• On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• Coloring interval graphs with First-Fit
• On some packing problem related to dynamic storage allocation
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(23)

• A Dichotomy Theorem for First-Fit Chain Partitions
• Batch Coloring of Graphs
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• Forbidden structures for efficient first-fit chain partitioning (extended abstract)
• A refined analysis of online path coloring in trees
• On the max coloring problem
• Online coloring of short intervals
• Computational aspects of greedy partitioning of graphs
• Reverse mathematics and Grundy colorings of graphs
• Max-coloring of vertex-weighted graphs
• On-line chain partitions of orders: a survey
• On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
• scientific article; zbMATH DE number 7758354 (Why is no real title available?)
• On Computational Aspects of Greedy Partitioning of Graphs
• First-fit coloring on interval graphs has performance ratio at least 5
• On-line dimension for posets excluding two long incomparable chains
• First-fit coloring of bounded tolerance graphs
• Grundy distinguishes treewidth from pathwidth
• First-Fit is linear on posets excluding two long incomparable chains
• An easy subexponential bound for online chain partitioning
• Coloring interval graphs with First-Fit
• Batch coloring of graphs
• Grundy Distinguishes Treewidth from Pathwidth

This page was built for publication: A note on 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 Q925259)