Minimum-delay schedules in layered networks

DOI10.1007/BF01178583MaRDI QIDQ1812948zbMATH OpenFDO

Authors Daniel P. Bovet, Pilu Crescenzi

Publication date 25 June 1992

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01178583

zbMATH Keywords

layered networkroutingscheduling problem

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Review text

We consider the following problem: Given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomial time algorithms.

Recommendations

• OPTIMUM SCHEDULE PROBLEMS IN STORE AND FORWARD NETWORKS
• Scheduling transmissions in a network
• Transmissions in a network with capacities and delays
• Single path routing with delay considerations

Cites work

• A switching algorithm for the solution of quadratic Boolean equations
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Scheduling File Transfers

Cited in

(7)

• A polynomial-time algorithm for message routing in hierarchical communication networks
• Scheduling problems in transportation networks of line topology
• Real-Time Message Routing and Scheduling
• Scheduling transmissions in a network
• Single path routing with delay considerations
• OPTIMUM SCHEDULE PROBLEMS IN STORE AND FORWARD NETWORKS
• Construction of a Minimum Complexity Onboard Switched Network with Time Synchronization

This page was built for publication: Minimum-delay schedules in layered networks

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