2012/10/28 by Ali Ghiasian, Ghiasian, Ali, Behnaz Omoomi +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1210.7467
arxiv created 2012/10/28 · arxiv updated 2012/10/30
In single channel wireless networks, concurrent transmission at different links may interfere with each other. To improve system throughput, a scheduling algorithm is necessary to choose a subset of links at each time slot for data trasmission. Throughput optimal link scheduling discipline in such a wireless network is generally an NP-hard problem. In this paper, we develop a poylnomial time algorithm for link scheduling problem provided that network conflict graph is line multigraph. (i.e. line graph for which its root graph is multigraph). This result can be a guideline for network designers to plan the topology of a stationary wireless network such that the required conditions hold and then the throughput optimal algorithm can be run in a much less time.