Optimal Broadcast Scheduling in Packet Radio Networks via Branch and Price

References

• Balas E., Xue J. Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. (1991) 20:209–221Crossref, Google Scholar
• Barrett C., Istrate G., Kumar V., Marathe M., Thite S., Thulasidasan S. Strong edge coloring for channel assignment in wireless radio networks. Proc. 4th IEEE Conf. Pervasive Comput. Comm. Workshops (PERCOMW'06) (2006) (IEEE Computer Society, Washington, D.C.) 106–110Crossref, Google Scholar
• Brown J. Chromatic scheduling and the chromatic number problem. Management Sci. (1972) 19:456–463Link, Google Scholar
• Chen J., Wang Y., Chen J. A novel broadcast scheduling strategy using factor graphs and the sum-product algorithm. IEEE Trans. Wireless Comm. (2006) 5:1241–1249Crossref, Google Scholar
• Dantzig G., Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8:101–111Link, Google Scholar
• El-Hoiydi A. Spatial TDMA and CSMA with preamble sampling for low power ad-hoc wireless sensor networks. IEEE Sympos. Comput. Comm. (ISCC) (2002) Taormina, Italy(IEEE Computer Society, Washington, D.C.) 685–692Crossref, Google Scholar
• Ephremides A., Truong T. Scheduling broadcasts in multihop radio networks. IEEE Trans. Comm. (1990) 38:456–460Crossref, Google Scholar
• Garey M., Johnson D. The complexity of near-optimal graph coloring. J. Assoc. Comput. Machinery (1976) 23:43–49Crossref, Google Scholar
• Gebremedhin A., Manne F., Pothen A. Parallel distance-k coloring algorithms for numerical optimization. ESA '02: Proc. 10th Annual Eur. Sympos. Algorithms (2002) (Springer-Verlag, London) 736–747Crossref, Google Scholar
• Gilmore P., Gomory R. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9:849–859Link, Google Scholar
• Gilmore P., Gomory R. A linear programming approach to the cutting stock problem—Part II. Oper. Res. (1963) 11:863–888Link, Google Scholar
• ILOGCPLEX 8.1 User's Manual (2002) (ILOG, Inc., Gentilly, France) Google Scholar
• Krumke S., Marathe M., Ravi S. Models and approximation algorithms for channel assignment in radio networks. Wireless Networks (2001) 7:575–584Crossref, Google Scholar
• Mehrotra A., Trick M. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8:344–354Link, Google Scholar
• Molloy M., Salavatipour M. Frequency channel assignment on planar networks. Euro-Par '02: Proc. 8th Internat. Euro-Par Conf. Parallel Processing. (2002) (Springer-Verlag, London) 912–921Crossref, Google Scholar
• Ramanathan R., Lloyd E. On the complexity of distance-2 coloring. Proc. 4th Internat. Conf. Comput. Inform. (ICCI) (1992) Toronto:71–74Google Scholar
• Ramanathan R., Lloyd E. Scheduling algorithms for multi-hop radio networks. IEEE/ACM Trans. Networking (TON) (1993) 1:166–172Crossref, Google Scholar
• Salcedo-Sanz S., Bousoño Calzón C., Figueiras-Vidal A. A mixed neural-genetic algorithm for the broadcast scheduling problem. IEEE Trans. Wireless Comm. (2003) 2:277–283Crossref, Google Scholar
• Sen A., Capone J. Scheduling in packet radio networks—A new approach. Proc. IEEE GlobeCom, Rio De Janeiro (1999) Crossref, Google Scholar
• Sen A., Huson M. A new model for scheduling packet radio networks. Wireless Networks (1997) 3:71–82Crossref, Google Scholar
• Sen A., Malesinska E. Approximation algorithms for radio network scheduling. Proc. 35th Conf. Comm., Control Comput. (1997) Champaign, IL:573–582Google Scholar
• Somarriba O., Giles T. Transmission power control for spatial TDMA in wireless radio networks. Proc. 4th IEEE Conf. Mobile Wireless Comm. Networks, Stockholm (2002) Google Scholar
• van den Heuvel J., McGuinness S. Coloring the square of a planar graph. J. Graph Theory (2003) 42:110–124Crossref, Google Scholar
• Vance P. Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optim. Appl. (1998) 9:211–228Crossref, Google Scholar
• Vanderbeck F., Wolsey L. An exact algorithm for IP column generation. Oper. Res. Lett. (1996) 19:151–159Crossref, Google Scholar
• Wang G., Ansari N. Optimal broadcast scheduling in packet radio networks using mean field annealing. IEEE J. Selected Areas Comm. (1997) 15:250–260Crossref, Google Scholar
• Wang L., Shi H. A gradual noisy chaotic neural network for solving the broadcast scheduling problem in packet radio networks. IEEE Trans. Neural Networks (2006) 17:989–1000Crossref, Google Scholar
• Yeo J., Lee H., Kim S. An efficient broadcast scheduling algorithm for TDMA ad-hoc networks. Comput. Oper. Res. (2002) 29:1793–1806Crossref, Google Scholar