Link scheduling in polynomial time

DOI10.1109/18.21215MaRDI QIDQ3826350zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bruce Hajek, Galen Sasaki

Publication date 1988

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1f128b9e521adc4a5097d16bf9b24aad47ab4e51

zbMATH Keywords

messagespolynomial time algorithmsscheduling conversationsspread spectrum radio network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Publication:4203989
• Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks
• Approximation algorithms for time-constrained scheduling on line networks
• Scheduling time-constrained communication in linear networks
• Scheduling in synchronous networks and the greedy algorithm
• scientific article; zbMATH DE number 1377367
• Polynomial-time approximation schemes for scheduling problems with time lags
• Hardness of Low Delay Network Scheduling
• Algorithms and Computation
• Competitive Analysis of Scheduling Algorithms for Aggregated Links

Cited in

(30)

• Data transfers in networks
• A polynomial-time algorithm for message routing in hierarchical communication networks
• Computing the optimal IO sequences of a protocol in polynomial time
• Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models
• Optimal scheduling in CDMA packet radio networks
• Optimal consistent network updates in polynomial time
• A near-optimal optimization algorithm for link assignment in wireless ad-hoc networks
• A maximum clique based approximation algorithm for wireless link scheduling under SINR model
• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model
• Optimal edge-coloring with edge rate constraints
• On the Complexity of Scheduling in Half-Duplex Diamond Networks
• Round weighting problem and gathering in radio networks with symmetrical interference
• scientific article; zbMATH DE number 3884101 (Why is no real title available?)
• Queue-proportional rate allocation with per-link information in multihop wireless networks
• An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models
• Scheduling transmissions in a network
• Optimal scaling of average queue sizes in an input-queued switch: an open problem
• Link scheduling in wireless sensor networks: distributed edge-coloring revisited
• ON SOLVING MULTIMESSAGE MULTICASTING PROBLEMS
• Distance edge coloring and collision-free communication in wireless sensor networks
• Towards the Chen-Raspaud conjecture
• Optimization architecture for joint multi-path routing and scheduling in wireless mesh networks
• Multi-channel assignment and link scheduling for prioritized latency-sensitive applications
• A robust multi-priority topology-independent transmission schedule for packet radio networks
• A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model
• A combinatorial algorithm for the TDMA message scheduling problem
• Polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems
• Approximate dynamic programming for link scheduling in wireless mesh networks
• Competitive analysis of scheduling algorithms for aggregated links
• The performance of an upper bound on the fractional chromatic number of weighted graphs

This page was built for publication: Link scheduling in polynomial time

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