An Almost-Linear Algorithm for Two-Processor Scheduling

DOI10.1145/322326.322335zbMATH Open0485.68034OpenAlexW1996256520MaRDI QIDQ3945581FDOQ3945581

Authors: Harold N. Gabow 

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322326.322335

zbMATH Keywords

directed acyclic graphshighest-level-first schedulingcritical path schedulinggraph algorithms, precedence constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited In (24)

• Scheduling chains on uniform processors with communication delays
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• Parallel maximum matching algorithms in interval graphs
• Planar stage graphs: Characterizations and applications
• Non-preemptive profile scheduling and quasi-interval orders
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• An inherently iterative computation of Ackermann's function
• ON OPTIMAL LOOP UNROLLING IN TWO-PROCESSOR SCHEDULING
• Scheduling Opposing Forests
• A note on scheduling multiprocessor tasks with precedence constraints on parallel processors
• A state-of-the-art review of parallel-machine scheduling research
• A linear-time algorithm for a special case of disjoint set union
• A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations
• Applications of scheduling theory to formal language theory
• Minimizing the number of stations and station activation costs for a production line
• Optimal shooting: Characterizations and applications
• Profile Scheduling of Opposing Forests and Level Orders
• Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization
• Scheduling unit-length jobs with precedence constraints of small height
• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
• An efficient algorithm for finding ideal schedules
• An efficient parallel algorithm for scheduling interval ordered tasks
• Normal-form preemption sequences for an open problem in scheduling theory

This page was built for publication: An Almost-Linear Algorithm for Two-Processor Scheduling

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