File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Scheduling in synchronous networks and the greedy algorithm

TitleScheduling in synchronous networks and the greedy algorithm
Authors
KeywordsGreedy Algorithms
Scheduling Algorithms
Synchronous Networks
Issue Date1999
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 1999, v. 220 n. 1, p. 157-183 How to Cite?
AbstractWe study the greedy algorithm for delivering messages with deadlines in synchronous networks. The processors have to determine a feasible schedule, by which all messages will arrive at their destinations and meet their deadlines. At each step a processor cannot send on any of its leaving links more messages than the capacity of that link. We study bottleneck-free networks, in which the capacity of each edge leaving any processor is at least the sum of the capacities of the edges entering it. For such networks where there is at most one simple path connecting any pair of vertices, we determine a necessary and sufficient condition for the initial configuration to have a feasible schedule, and prove that if this condition holds then the greedy algorithm, that chooses at each step the most urgent messages (those with closest deadlines), determines such a feasible schedule. We start with directed chain networks with unit capacities, and modify the results to general chains, directed rings, trees, and then for the general above-mentioned class of networks. For networks with a bottleneck and half-duplex networks we show that no algorithm, that makes decisions based only on local information, can solve the problem. For bottleneck-free networks, in which the messages between two processors have to follow only one of the paths connecting them, the problem of deciding whether there exists a valid schedule is NP-complete. © 1999 Elsevier Science B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/154778
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLui, KSen_US
dc.contributor.authorZaks, Sen_US
dc.date.accessioned2012-08-08T08:30:37Z-
dc.date.available2012-08-08T08:30:37Z-
dc.date.issued1999en_US
dc.identifier.citationTheoretical Computer Science, 1999, v. 220 n. 1, p. 157-183en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/154778-
dc.description.abstractWe study the greedy algorithm for delivering messages with deadlines in synchronous networks. The processors have to determine a feasible schedule, by which all messages will arrive at their destinations and meet their deadlines. At each step a processor cannot send on any of its leaving links more messages than the capacity of that link. We study bottleneck-free networks, in which the capacity of each edge leaving any processor is at least the sum of the capacities of the edges entering it. For such networks where there is at most one simple path connecting any pair of vertices, we determine a necessary and sufficient condition for the initial configuration to have a feasible schedule, and prove that if this condition holds then the greedy algorithm, that chooses at each step the most urgent messages (those with closest deadlines), determines such a feasible schedule. We start with directed chain networks with unit capacities, and modify the results to general chains, directed rings, trees, and then for the general above-mentioned class of networks. For networks with a bottleneck and half-duplex networks we show that no algorithm, that makes decisions based only on local information, can solve the problem. For bottleneck-free networks, in which the messages between two processors have to follow only one of the paths connecting them, the problem of deciding whether there exists a valid schedule is NP-complete. © 1999 Elsevier Science B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectGreedy Algorithmsen_US
dc.subjectScheduling Algorithmsen_US
dc.subjectSynchronous Networksen_US
dc.titleScheduling in synchronous networks and the greedy algorithmen_US
dc.typeArticleen_US
dc.identifier.emailLui, KS:kslui@eee.hku.hken_US
dc.identifier.authorityLui, KS=rp00188en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0012919775en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0012919775&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume220en_US
dc.identifier.issue1en_US
dc.identifier.spage157en_US
dc.identifier.epage183en_US
dc.identifier.isiWOS:000080729000007-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridLui, KS=7103390016en_US
dc.identifier.scopusauthoridZaks, S=7003634440en_US
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats