Scheduling Interval-Ordered Tasks
From MaRDI portal
Publication:3854618
DOI10.1137/0208031zbMath0421.68040OpenAlexW2060983467MaRDI QIDQ3854618
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0208031
chordal graphsinterval ordersincomparability graphNP- completenesspolynomial in time algorithmsarbitrary length tasksscheduling unit length tasks
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Perfect edge domination and efficient edge domination in graphs, Profile Scheduling of Opposing Forests and Level Orders, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Schedule-induced posets, Analysis of scheduling problems with typed task systems, Applications of scheduling theory to formal language theory, Scheduling with constrained processor allocation for interval orders, A note on scheduling multiprocessor tasks with precedence constraints on parallel processors, Can transitive orientation make sandwich problems easier?, New linear time algorithms for generating perfect elimination orderings of chordal graphs, The jump number problem on interval orders: A 3/2 approximation algorithm, Adamant digraphs, Rational preemptive scheduling, Scheduling tasks with communication delays on parallel processors, Simultaneous representation of interval and interval-containment orders, ON CONSIDERING COMMUNICATION IN SCHEDULING TASK GRAPHS ON PARALLEL PROCESSORS, SCHEDULING INTERVAL ORDERS IN PARALLEL, Chain dominated orders, Unnamed Item, Scheduling unit-length jobs with precedence constraints of small height, The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable, Interval approximations of message causality in distributed executions, Satisfiability problems on intervals and unit intervals, Parallel \(N\)-free order recognition, Interval graphs with side (and size) constraints, A linear-time recognition algorithm for interval dags, A characterization of unit interval bigraphs of open and closed intervals, Tree-width and path-width of comparability graphs of interval orders, On domination elimination orderings and domination graphs, Scheduling chained multiprocessor tasks onto large multiprocessor system, Integral mixed unit interval graphs, Preemptive scheduling of interval orders is polynomial, An efficient parallel algorithm for scheduling interval ordered tasks, Some aspects of the semi-perfect elimination, Modeling recreational systems using optimization techniques and information technologies, Transitive closure for restricted classes of partial orders, UET-scheduling with constrained processor allocations, Restrictions of graph partition problems. I, Parallel interval order recognition and construction of interval representations, Batch processing with interval graph compatibilities between tasks, Unit Interval Graphs of Open and Closed Intervals, A linear time and space algorithm to recognize interval orders, Optimal preemptive scheduling on a fixed number of identical parallel machines, Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay., Unnamed Item, Mixed unit interval graphs, Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, Some approximation algorithms for the clique partition problem in weighted interval graphs, Preemptive scheduling and antichain polyhedra, A linear time recognition algorithm for proper interval graphs, Scheduling unitary task systems with zero--one communication delays for quasi-interval orders, Minimal vertex separators of chordal graphs, Optimal Scheduling on Parallel Processors with Precedence Constraints and General Costs, A polynomial algorithm for recognizing the \(\mathcal A\)-order class, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Scheduling Opposing Forests, Scheduling preemptive jobs with precedence constraints on parallel machines, Review of properties of different precedence graphs for scheduling problems, Some aspects of perfect elimination orderings in chordal graphs, Optimal scheduling on parallel machines for a new order class, A linear-time algorithm for a special case of disjoint set union, A setup heuristic for interval orders, Algorithms for dynamic scheduling of unit execution time tasks
