On the public citation graph

The Linearity of First-Fit Coloring of Interval Graphs

0 signed · 110 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/jgt.3190120212openalex-snapshot
On‐line and first fit colorings of graphs
inferredcites →https://doi.org/10.1016/0097-3165(76)90066-2openalex-snapshot
On Woodall's interval problem
inferredcites →https://doi.org/10.1017/s0022481200051549openalex-snapshot
Effective coloration
inferredcites →https://doi.org/10.1051/ita/1988220404871openalex-snapshot
On some packing problem related to dynamic storage allocation

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/9781118032497.ch10openalex-snapshot
Algorithms
inferred← citeshttps://doi.org/10.1007/11523468_49openalex-snapshot
Online Interval Coloring and Variants
inferred← citeshttps://doi.org/10.1007/11549345_26openalex-snapshot
Online Interval Coloring with Packing Constraints
inferred← citeshttps://doi.org/10.1007/11758471_28openalex-snapshot
On-Line Coloring of H-Free Bipartite Graphs
inferred← citeshttps://doi.org/10.1007/11785293_6openalex-snapshot
Variable Sized Online Interval Coloring with Bandwidth
inferred← citeshttps://doi.org/10.1007/3-540-46784-x_2openalex-snapshot
Online Algorithms: A Study of Graph-Theoretic Concepts
inferred← citeshttps://doi.org/10.1007/3-540-51486-4_93openalex-snapshot
A coloring algorithm for interval graphs
inferred← citeshttps://doi.org/10.1007/3-540-57273-2_43openalex-snapshot
On bufferless routing of variable-length messages in leveled networks
inferred← citeshttps://doi.org/10.1007/3-540-61680-2_46openalex-snapshot
Approximation algorithms for dynamic storage allocation
inferred← citeshttps://doi.org/10.1007/3-540-63397-9_29openalex-snapshot
Dynamic storage allocation with known durations
inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_264openalex-snapshot
Online Interval Coloring
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_31openalex-snapshot
Parameterized Approximation
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_264openalex-snapshot
Online Interval Coloring
inferred← citeshttps://doi.org/10.1007/978-3-030-39479-0_7openalex-snapshot
An Improved Upper Bound for the Ring Loading Problem
inferred← citeshttps://doi.org/10.1007/978-3-032-06706-7_11openalex-snapshot
On the FirstFit Algorithm for Online Unit-Interval Coloring
inferred← citeshttps://doi.org/10.1007/978-3-540-24592-6_1openalex-snapshot
Online Coloring of Intervals with Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-540-27798-9_37openalex-snapshot
New Approximation Algorithms for Some Dynamic Storage Allocation Problems
inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_2openalex-snapshot
Online Problems, Pathwidth, and Persistence
inferred← citeshttps://doi.org/10.1007/978-3-540-30550-7_2openalex-snapshot
Some New Directions and Questions in Parameterized Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_21openalex-snapshot
Online Conflict-Free Colorings for Hypergraphs
inferred← citeshttps://doi.org/10.1007/978-3-540-74450-4_22openalex-snapshot
Online Capacitated Interval Coloring
inferred← citeshttps://doi.org/10.1007/978-3-540-77918-6_12openalex-snapshot
On the Max Coloring Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-17514-5_19openalex-snapshot
Single and Multiple Device DSA Problem, Complexities and Online Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_264-2openalex-snapshot
Online Interval Coloring
inferred← citeshttps://doi.org/10.1007/978-3-642-35843-2_26openalex-snapshot
Online and Quasi-online Colorings of Wedges and Intervals
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_79openalex-snapshot
A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem
inferred← citeshttps://doi.org/10.1007/978-3-662-53174-7_2openalex-snapshot
Open Problems on Graph Coloring for Special Graph Classes
inferred← citeshttps://doi.org/10.1007/bf01206361openalex-snapshot
Effective on-line coloring ofP 5-free graphs
inferred← citeshttps://doi.org/10.1007/bf01271267openalex-snapshot
On-line coloring of perfect graphs
inferred← citeshttps://doi.org/10.1007/bf01294263openalex-snapshot
Coloring inductive graphs on-line
inferred← citeshttps://doi.org/10.1007/bfb0029574openalex-snapshot
Coloring graphs on-line
inferred← citeshttps://doi.org/10.1007/s00453-007-9071-0openalex-snapshot
Variable Sized Online Interval Coloring with Bandwidth
inferred← citeshttps://doi.org/10.1007/s00453-022-01043-6openalex-snapshot
Improved Algorithms for Scheduling Unsplittable Flows on Paths
inferred← citeshttps://doi.org/10.1007/s10951-015-0434-0openalex-snapshot
A graph coloring approach to the deployment scheduling and unit assignment problem
inferred← citeshttps://doi.org/10.1007/s11083-008-9076-6openalex-snapshot
A Note on First-Fit Coloring of Interval Graphs
inferred← citeshttps://doi.org/10.1007/s11083-010-9184-yopenalex-snapshot
First-Fit is Linear on Posets Excluding Two Long Incomparable Chains
inferred← citeshttps://doi.org/10.1007/s11083-011-9197-1openalex-snapshot
On-Line Chain Partitions of Orders: A Survey
inferred← citeshttps://doi.org/10.1007/s11083-011-9222-4openalex-snapshot
On-Line Dimension for Posets Excluding Two Long Incomparable Chains
inferred← citeshttps://doi.org/10.1016/0012-365x(89)90096-4openalex-snapshot
An on-line graph coloring algorithm with sublinear performance ratio
inferred← citeshttps://doi.org/10.1016/0012-365x(91)90011-popenalex-snapshot
A polynomial time approximation algorithm for dynamic storage allocation
inferred← citeshttps://doi.org/10.1016/0012-365x(94)00285-qopenalex-snapshot
Coloring interval graphs with first-fit
inferred← citeshttps://doi.org/10.1016/0012-365x(94)90139-2openalex-snapshot
On the mean chromatic number
inferred← citeshttps://doi.org/10.1016/0012-365x(95)00189-4openalex-snapshot
On the on-line chromatic number of the family of on-line 3-chromatic graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90209-eopenalex-snapshot
The greedy algorithm is optimal for on-line edge coloring
inferred← citeshttps://doi.org/10.1016/0890-5401(92)90012-5openalex-snapshot
The online graph bandwidth problem
inferred← citeshttps://doi.org/10.1016/j.dam.2007.07.002openalex-snapshot
Inequalities for the Grundy chromatic number of graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2010.05.002openalex-snapshot
First-Fit coloring of bounded tolerance graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2018.09.021openalex-snapshot
On spectrum assignment in elastic optical tree-networks
inferred← citeshttps://doi.org/10.1016/j.disc.2012.03.029openalex-snapshot
First-fit chromatic numbers of d -degenerate graphs
inferred← citeshttps://doi.org/10.1016/j.ejc.2012.07.007openalex-snapshot
On first-fit coloring of ladder-free posets
inferred← citeshttps://doi.org/10.1016/j.ejc.2015.05.015openalex-snapshot
First-fit coloring on interval graphs has performance ratio at least 5
inferred← citeshttps://doi.org/10.1016/j.ejc.2020.103202openalex-snapshot
On-line partitioning of width w posets into wO(loglogw) chains
inferred← citeshttps://doi.org/10.1016/j.endm.2011.09.030openalex-snapshot
Forbidden structures for efficient First-Fit chain partitioning (extended abstract)
inferred← citeshttps://doi.org/10.1016/j.entcs.2005.06.028openalex-snapshot
Variants of Online Chain Partition Problem of Posets
inferred← citeshttps://doi.org/10.1016/j.ipl.2005.07.001openalex-snapshot
Bounded families for the on-line t-relaxed coloring
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.08.006openalex-snapshot
A note on the online First-Fit algorithm for coloring k-inductive graphs
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.08.002openalex-snapshot
Online promise problems with online width metrics
inferred← citeshttps://doi.org/10.1016/j.jda.2017.07.001openalex-snapshot
Optimizing bandwidth allocation in elastic optical networks with application to scheduling
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.05.018openalex-snapshot
Online interval coloring with packing constraints
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.11.005openalex-snapshot
Single and multiple device DSA problems, complexities and online algorithms
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.07.037openalex-snapshot
On the max coloring problem
inferred← citeshttps://doi.org/10.1016/s0020-0190(00)00109-5openalex-snapshot
On the performance of the first-fit coloring algorithm on permutation graphs
inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00002-1openalex-snapshot
A coloring problem for weighted graphs
inferred← citeshttps://doi.org/10.1016/s0049-237x(98)80051-7openalex-snapshot
Chapter 18 Recursive and on-line graph coloring
inferred← citeshttps://doi.org/10.1016/s0166-218x(00)00309-7openalex-snapshot
An approximation result for a periodic allocation problem
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00175-4openalex-snapshot
Dynamic storage allocation with known durations
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00025-0openalex-snapshot
Ondashline routing in all-optical networks
inferred← citeshttps://doi.org/10.1017/cbo9780511662119.009openalex-snapshot
New Perspectives on Interval Orders and Interval Graphs
inferred← citeshttps://doi.org/10.1017/s0963548309990587openalex-snapshot
Online Conflict-Free Colouring for Hypergraphs
inferred← citeshttps://doi.org/10.1093/jigpal/jzac065openalex-snapshot
Online, computable and punctual structure theory
inferred← citeshttps://doi.org/10.1109/12.506427openalex-snapshot
On bufferless routing of variable length messages in leveled networks
inferred← citeshttps://doi.org/10.1109/focs.2010.40openalex-snapshot
The Sub-exponential Upper Bound for On-Line Chain Partitioning
inferred← citeshttps://doi.org/10.1109/fscs.1990.89568openalex-snapshot
Coloring inductive graphs on-line
inferred← citeshttps://doi.org/10.1109/ipdps.2014.93openalex-snapshot
Optimizing Bandwidth Allocation in Flex-Grid Optical Networks with Application to Scheduling
inferred← citeshttps://doi.org/10.1137/060668675openalex-snapshot
A New Algorithm for On-line Coloring Bipartite Graphs
inferred← citeshttps://doi.org/10.1137/060672479openalex-snapshot
On the First-Fit Chromatic Number of Graphs
inferred← citeshttps://doi.org/10.1137/070682496openalex-snapshot
Online Capacitated Interval Coloring
inferred← citeshttps://doi.org/10.1137/090753863openalex-snapshot
First-Fit Algorithm for the On-Line Chain Partitioning Problem
inferred← citeshttps://doi.org/10.1137/110854394openalex-snapshot
First-Fit Coloring of Incomparability Graphs
inferred← citeshttps://doi.org/10.1137/110855806openalex-snapshot
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
inferred← citeshttps://doi.org/10.1137/20m1319395openalex-snapshot
An Improved Upper Bound for the Ring Loading Problem
inferred← citeshttps://doi.org/10.1137/s0097539703423941openalex-snapshot
OPT Versus LOAD in Dynamic Storage Allocation
inferred← citeshttps://doi.org/10.1137/s0895480191218861openalex-snapshot
On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
inferred← citeshttps://doi.org/10.1137/s0895480192224737openalex-snapshot
On-Line Coloring and Recursive Graph Theory
inferred← citeshttps://doi.org/10.1137/s089548019325647xopenalex-snapshot
Tight Bounds for Dynamic Storage Allocation
inferred← citeshttps://doi.org/10.1137/s089548019631030xopenalex-snapshot
On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
inferred← citeshttps://doi.org/10.1142/s1793830922500422openalex-snapshot
On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
inferred← citeshttps://doi.org/10.1145/1064546.1180619openalex-snapshot
Approximating interval coloring and max-coloring in chordal graphs
inferred← citeshttps://doi.org/10.1145/1978782.1978790openalex-snapshot
Max-coloring and online coloring with bandwidths on interval graphs
inferred← citeshttps://doi.org/10.1145/2133382.2133387openalex-snapshot
Comparability Graph Coloring for Optimizing Utilization of Software-Managed Stream Register Files for Stream Processors
inferred← citeshttps://doi.org/10.1145/780542.780624openalex-snapshot
OPT versus LOAD in dynamic storage allocation
inferred← citeshttps://doi.org/10.11606/d.45.2011.tde-09022012-151736openalex-snapshot
Algoritmos para o problema da cobertura por sensores
inferred← citeshttps://doi.org/10.1587/transfun.e99.a.1885openalex-snapshot
A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring
inferred← citeshttps://doi.org/10.17760/d20316237openalex-snapshot
Scheduling flows and coflows in networks
inferred← citeshttps://doi.org/10.18297/etd/3974openalex-snapshot
The on-line width of various classes of posets.
inferred← citeshttps://doi.org/10.24132/jwscg.2023.7openalex-snapshot
A Resource Allocation Algorithm for a History-Aware Frame Graph
inferred← citeshttps://doi.org/10.32657/10220/46906openalex-snapshot
Combinatorial algorithms for scheduling jobs to minimize server usage time
inferred← citeshttps://doi.org/10.37236/7231openalex-snapshot
An Easy Subexponential Bound for Online Chain Partitioning
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2012.267openalex-snapshot
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2020.86openalex-snapshot
Breaking the Barrier of 2 for the Storage Allocation Problem
inferred← citeshttps://doi.org/10.46298/dmtcs.2083openalex-snapshot
Generalized dynamic storage allocation
inferred← citeshttps://doi.org/10.46298/dmtcs.391openalex-snapshot
A lower bound for approximating the Grundy number
inferred← citeshttps://doi.org/10.48550/arxiv.1402.1107openalex-snapshot
Approximation Algorithms for Covering and Packing Problems on Paths
inferred← citeshttps://doi.org/10.48550/arxiv.1810.00270openalex-snapshot
On-line partitioning of width w posets into w^O(log log w) chains
inferred← citeshttps://doi.org/10.5555/982792.982876openalex-snapshot
Buffer minimization using max-coloring
inferred← citeshttps://doi.org/10.70675/bc019e47z29d3z46baz8646za3d24cbd0cf0openalex-snapshot
Energy Minimization, Data Movement and Uncertainty : Models and Algorithms
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.