Link scheduling in polynomial time

DOI10.1109/18.21215zbMath0672.90069OpenAlexW2153086189WikidataQ56391144 ScholiaQ56391144MaRDI QIDQ3826350

Galen Sasaki, Bruce Hajek

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

polynomial time algorithmsmessagesscheduling conversationsspread spectrum radio network

Mathematics Subject Classification ID

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

Related Items

A combinatorial algorithm for the TDMA message scheduling problem ⋮ Round weighting problem and gathering in radio networks with symmetrical interference ⋮ Data transfers in networks ⋮ 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 ⋮ Distance edge coloring and collision‐free communication in wireless sensor networks ⋮ Optimal scaling of average queue sizes in an input-queued switch: an open problem ⋮ 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 ⋮ Towards the Chen-Raspaud conjecture ⋮ Link scheduling in wireless sensor networks: distributed edge-coloring revisited ⋮ Optimization architecture for joint multi-path routing and scheduling in wireless mesh networks ⋮ Approximate dynamic programming for link scheduling in wireless mesh networks ⋮ The performance of an upper bound on the fractional chromatic number of weighted graphs ⋮ A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model ⋮ A near-optimal optimization algorithm for link assignment in wireless ad-hoc networks ⋮ Optimal edge-coloring with edge rate constraints ⋮ ON SOLVING MULTIMESSAGE MULTICASTING PROBLEMS ⋮ Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models