A linear-time recognition algorithm for interval dags

DOI10.1016/0020-0190(81)90069-7zbMath0454.68011OpenAlexW2115599154MaRDI QIDQ1149762

Harold N. Gabow

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90069-7

zbMATH Keywords

schedulinginterval ordertransitive closure

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Profile Scheduling of Opposing Forests and Level Orders, The jump number problem on interval orders: A 3/2 approximation algorithm, Chain dominated orders, Scheduling unit-length jobs with precedence constraints of small height, On-line algorithms for orders, Parallel \(N\)-free order recognition, Tree-width and path-width of comparability graphs of interval orders, Split orders, Parallel interval order recognition and construction of interval representations, Note on scheduling intervals on-line, Review of properties of different precedence graphs for scheduling problems, A linear-time algorithm for a special case of disjoint set union

Cites Work

• Scheduling Interval-Ordered Tasks
• Efficiency of a Good But Not Linear Set Union Algorithm
• Scheduling Graphs on Two Processors
• Unnamed Item
• Unnamed Item