{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:13:18Z","timestamp":1767982398447,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,9,7]],"date-time":"2010-09-07T00:00:00Z","timestamp":1283817600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Wireless Com Network"],"published-print":{"date-parts":[[2010,12]]},"DOI":"10.1155\/2010\/418934","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T19:45:14Z","timestamp":1286307914000},"source":"Crossref","is-referenced-by-count":29,"title":["On the Complexity of Scheduling in Wireless Networks"],"prefix":"10.1186","volume":"2010","author":[{"given":"Changhee","family":"Joo","sequence":"first","affiliation":[]},{"given":"Gaurav","family":"Sharma","sequence":"additional","affiliation":[]},{"given":"Ness B.","family":"Shroff","sequence":"additional","affiliation":[]},{"given":"Ravi R.","family":"Mazumdar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,7]]},"reference":[{"issue":"12","key":"1902_CR1","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1109\/9.182479","volume":"37","author":"L Tassiulas","year":"1992","unstructured":"Tassiulas L, Ephremides A: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 1992, 37(12):1936-1948. 10.1109\/9.182479","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"7","key":"1902_CR2","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1109\/TCOMM.2004.831346","volume":"52","author":"L Xiao","year":"2004","unstructured":"Xiao L, Johansson M, Boyd SP: Simultaneous routing and resource allocation via dual decomposition. IEEE Transactions on Communications 2004, 52(7):1136-1144. 10.1109\/TCOMM.2004.831346","journal-title":"IEEE Transactions on Communications"},{"issue":"1","key":"1902_CR3","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1109\/TNET.2002.808401","volume":"11","author":"MJ Neely","year":"2003","unstructured":"Neely MJ, Modiano E, Rohrs CE: Power allocation and routing in multibeam satellites with time-varying channels. IEEE\/ACM Transactions on Networking 2003, 11(1):138-152. 10.1109\/TNET.2002.808401","journal-title":"IEEE\/ACM Transactions on Networking"},{"issue":"1","key":"1902_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/18.108264","volume":"38","author":"L Tassiulas","year":"1992","unstructured":"Tassiulas L, Ephremides A: Jointly optimal routing and scheduling in packet radio networks. IEEE Transactions on Information Theory 1992, 38(1):165-168. 10.1109\/18.108264","journal-title":"IEEE Transactions on Information Theory"},{"key":"1902_CR5","first-page":"702","volume-title":"Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03)","author":"RL Cruz","year":"2003","unstructured":"Cruz RL, Santhanam AV: Optimal routing, link scheduling and power control in multi-hop wireless networks. Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03), April 2003 702-711."},{"issue":"3","key":"1902_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1057\/palgrave.jors.2600523","volume":"49","author":"FP Kelly","year":"1998","unstructured":"Kelly FP, Maulloo AK, Tan D: Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 1998, 49(3):237-252.","journal-title":"Journal of the Operational Research Society"},{"issue":"5","key":"1902_CR7","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1109\/90.879352","volume":"8","author":"H Ya\u00efche","year":"2000","unstructured":"Ya\u00efche H, Mazumdar RR, Rosenberg C: A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE\/ACM Transactions on Networking 2000, 8(5):667-678. 10.1109\/90.879352","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"1902_CR8","doi-asserted-by":"publisher","first-page":"1804","DOI":"10.1109\/INFCOM.2005.1498460","volume":"3","author":"X Lin","year":"2005","unstructured":"Lin X, Shroff NB: The impact of imperfect scheduling on cross-layer rate control in wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '05), March 2005 3: 1804-1814.","journal-title":"Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '05)"},{"key":"1902_CR9","volume-title":"Proceedings of the 25th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '06)","author":"X Wu","year":"2006","unstructured":"Wu X, Srikant R: Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. Proceedings of the 25th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '06), April 2006"},{"issue":"4","key":"1902_CR10","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s11134-005-1450-0","volume":"50","author":"AL Stolyar","year":"2005","unstructured":"Stolyar AL: Maximizing queueing network utility subject to stability: greedy primal-dual algorithm. Queueing Systems 2005, 50(4):401-457. 10.1007\/s11134-005-1450-0","journal-title":"Queueing Systems"},{"key":"1902_CR11","volume-title":"Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications","author":"B Miller","year":"2000","unstructured":"Miller B, Bisdikian C: Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications. Prentice-Hall; 2000."},{"issue":"5","key":"1902_CR12","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1109\/18.21215","volume":"34","author":"B Hajek","year":"1988","unstructured":"Hajek B, Sasaki G: Link scheduling in polynomial time. IEEE Transactions on Information Theory 1988, 34(5):910-917. 10.1109\/18.21215","journal-title":"IEEE Transactions on Information Theory"},{"key":"1902_CR13","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA '90)","author":"HN Gabow","year":"1990","unstructured":"Gabow HN: Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the Symposium on Discrete Algorithms (SODA '90), 1990"},{"issue":"6","key":"1902_CR14","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1109\/JSAC.2004.830909","volume":"22","author":"H Balakrishnan","year":"2004","unstructured":"Balakrishnan H, Barrett CL, Kumar VSA, Marathe MV, Thite S: The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications 2004, 22(6):1069-1079. 10.1109\/JSAC.2004.830909","journal-title":"IEEE Journal on Selected Areas in Communications"},{"issue":"2","key":"1902_CR15","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1109\/TIT.2007.913537","volume":"54","author":"P Chaporkar","year":"2008","unstructured":"Chaporkar P, Kar K, Luo X, Sarkar S: Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Transactions on Information Theory 2008, 54(2):572-594.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"1902_CR16","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/1140103.1140283","volume":"34","author":"E Modiano","year":"2006","unstructured":"Modiano E, Shah D, Zussman G: Maximizing throughput in wireless networks via gossiping. Performance Evaluation Review 2006, 34(1):27-38. 10.1145\/1140103.1140283","journal-title":"Performance Evaluation Review"},{"key":"1902_CR17","first-page":"313","volume-title":"Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (Sigmetrics '07)","author":"S Sanghavi","year":"2007","unstructured":"Sanghavi S, Bui L, Srikant R: Distributed link scheduling with constant overhead. Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (Sigmetrics '07), June 2007 313-324."},{"key":"1902_CR18","volume-title":"Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing","author":"G Sharma","year":"2006","unstructured":"Sharma G, Joo C, Shroff NB: Distributed scheduling schemes for throughput guarantees in wireless networks. Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing, September 2006"},{"issue":"2","key":"1902_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/TAC.2008.2010888","volume":"54","author":"X Lin","year":"2009","unstructured":"Lin X, Rasool SB: Constant-time distributed scheduling policies for ad hoc wireless networks. IEEE Transactions on Automatic Control 2009, 54(2):231-242.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"1902_CR20","first-page":"19","volume-title":"Proceedings of the 26th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '07)","author":"C Joo","year":"2007","unstructured":"Joo C, Shroff NB: Performance of random access scheduling schemes in multi-hop wireless networks. Proceedings of the 26th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '07), May 2007 19-27."},{"issue":"1","key":"1902_CR21","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer LJ, Vazirani VV: NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters 1982, 15(1):14-19. 10.1016\/0020-0190(82)90077-1","journal-title":"Information Processing Letters"},{"key":"1902_CR22","volume-title":"On the complexity of scheduling in wireless networks","author":"C Joo","year":"2010","unstructured":"Joo C, Sharma G, Mazumdar RR, Shroff NB: On the complexity of scheduling in wireless networks. Korea University of Technology and Education; 2010.http:\/\/netlab.kut.ac.kr"},{"key":"1902_CR23","first-page":"70","volume-title":"Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '06)","author":"G Sharma","year":"2006","unstructured":"Sharma G, Mazumdar RR, Shroff NB: Maximum weighted matching with interference constraints. Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '06), March 2006 70-74."},{"issue":"4","key":"1902_CR24","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J Gill","year":"1977","unstructured":"Gill J: Computational complexity of probabilistic turing machines. SIAM Journal on Computing 1977, 6(4):675-695. 10.1137\/0206049","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1902_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J:Clique is hard to approximate within . Acta Mathematica 1999, 182(1):105-142. 10.1007\/BF02392825","journal-title":"Acta Mathematica"},{"issue":"1","key":"1902_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson MM: Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications 2000, 4(1):1-16.","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"6","key":"1902_CR27","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1023\/A:1012311216333","volume":"7","author":"SO Krumke","year":"2001","unstructured":"Krumke SO, Marathe MV, Ravi SS: Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 2001, 7(6):575-584. 10.1023\/A:1012311216333","journal-title":"Wireless Networks"},{"key":"1902_CR28","volume-title":"Points, spheres, and separators, a unified geometric approach to graph separators, Ph.D. thesis","author":"SH Teng","year":"1991","unstructured":"Teng SH: Points, spheres, and separators, a unified geometric approach to graph separators, Ph.D. thesis. School of Computer Science, Carnegie Mellon University, CMU-CS-91-184, Pittsburgh, Pa, USA; August 1991."},{"key":"1902_CR29","first-page":"69","volume-title":"Proceedings of the 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC '03)","author":"F Kuhn","year":"2003","unstructured":"Kuhn F, Wattenhofer R, Zollinger A: Ad-hoc networks beyond unit disk graphs. Proceedings of the 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC '03), September 2003, San Diego, Calif, USA 69-78."},{"issue":"1","key":"1902_CR30","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 1994, 41(1):153-180. 10.1145\/174644.174650","journal-title":"Journal of the ACM"},{"issue":"2","key":"1902_CR31","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt III","year":"1998","unstructured":"Hunt HB III, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 1998, 26(2):238-274. 10.1006\/jagm.1997.0903","journal-title":"Journal of Algorithms"},{"issue":"1","key":"1902_CR32","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Maass W: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 1985, 32(1):130-136. 10.1145\/2455.214106","journal-title":"Journal of the ACM"},{"issue":"4","key":"1902_CR33","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D Avis","year":"1983","unstructured":"Avis D: A survey of heuristics for the weighted matching problem. Networks 1983, 13(4):475-493. 10.1002\/net.3230130404","journal-title":"Networks"},{"issue":"2","key":"1902_CR34","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/90.222924","volume":"1","author":"S Ramanathan","year":"1993","unstructured":"Ramanathan S, Lloyd EL: Scheduling algorithms for multihop radio networks. IEEE\/ACM Transactions on Networking 1993, 1(2):166-177. 10.1109\/90.222924","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"1902_CR35","unstructured":"Hoepman J-H: Simple distributed weighted matchings. http:\/\/arxiv.org\/abs\/cs\/0410047v1"},{"key":"1902_CR36","first-page":"1103","volume-title":"Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '08)","author":"C Joo","year":"2008","unstructured":"Joo C, Lin X, Shroff NB: Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '08), April 2008 1103-1111."},{"key":"1902_CR37","first-page":"1128","volume-title":"Proceedings of the 46th IEEE Conference on Decision and Control (CDC '07)","author":"C Joo","year":"2007","unstructured":"Joo C, Lin X, Shroff NB: Performance limits of greedy maximal matching in multi-hop wireless networks. Proceedings of the 46th IEEE Conference on Decision and Control (CDC '07), December 2007 1128-1133."}],"container-title":["EURASIP Journal on Wireless Communications and Networking"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1155\/2010\/418934.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1155\/2010\/418934\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1155\/2010\/418934.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T19:15:55Z","timestamp":1565205355000},"score":1,"resource":{"primary":{"URL":"https:\/\/jwcn-eurasipjournals.springeropen.com\/articles\/10.1155\/2010\/418934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["1902"],"URL":"https:\/\/doi.org\/10.1155\/2010\/418934","relation":{},"ISSN":["1687-1499"],"issn-type":[{"value":"1687-1499","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,7]]},"article-number":"418934"}}