{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T01:24:06Z","timestamp":1755221046357,"version":"3.43.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Telecommunication Systems"],"published-print":{"date-parts":[[2003,1]]},"DOI":"10.1023\/a:1023426501170","type":"journal-article","created":{"date-parts":[[2003,6,6]],"date-time":"2003-06-06T13:42:07Z","timestamp":1054906927000},"page":"33-59","source":"Crossref","is-referenced-by-count":26,"title":["On the Complexity of Distributed Self-Configuration in Wireless Networks"],"prefix":"10.1007","volume":"22","author":[{"given":"Bhaskar","family":"Krishnamachari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Wicker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram\u00f3n","family":"B\u00e9jar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e8sar","family":"Fern\u00e0ndez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5119363_CR1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in: Proc. of 32nd Annual ACM Symposium on Theory of Computing, 2000.","DOI":"10.1145\/335305.335309"},{"key":"5119363_CR2","doi-asserted-by":"crossref","unstructured":"L. Bao and J.J. Garcia-Luna-Aceves, Collision-free topology-dependent channel access scheduling, in: 21st Century Military Communications Conference Proceedings, MILCOM 2000, pp. 507\u2013511.","DOI":"10.1109\/MILCOM.2000.905005"},{"key":"5119363_CR3","doi-asserted-by":"crossref","unstructured":"[Beame et al.] P. Beame et al., On the complexity of unsatisfiability proofs for random formulas, in:Proc. of 30th Annual ACM Symposium on Theory of Computing, 1998.","DOI":"10.1145\/276698.276870"},{"key":"5119363_CR4","unstructured":"R. Bejar et al., Distributed constraint satisfaction in a wireless sensor tracking system, in: Workshop on Distributed Constraint Reasoning, IJCAI-01, 2001."},{"key":"5119363_CR5","doi-asserted-by":"crossref","unstructured":"R. Bejar et al., Capturing structure with satisfiability, in: Proc. of 7th International Conference on Principles and Practice of Constraint Programming (CP2001), 2001.","DOI":"10.1007\/3-540-45578-7_10"},{"key":"5119363_CR6","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs (Academic Press, New York, 1985)."},{"key":"5119363_CR7","unstructured":"N. Bulusu et al., Scalable coordination for wireless sensor networks: Self-configuring localization systems, in: Proc. of the 6th International Symposium on Communication Theory and Applications (ISCTA'01), Ambleside, UK."},{"key":"5119363_CR8","unstructured":"J.C. Cano and P. Manzoni, A low power protocol to broadcast real-time data traffic in a clustered ad hoc network, in: Proc. of IEEE GlobeCom, 2001."},{"key":"5119363_CR9","unstructured":"G. Cao and M. Singhal, Efficient distributed channel allocation for mobile cellular networks, in: Proc. of 7th International Conference on Computer Communications and Networks, 1998, pp. 50\u201357."},{"key":"5119363_CR10","first-page":"331","volume":"1","author":"P. Cheeseman","year":"1991","unstructured":"P. Cheeseman, B. Kanefsky and W.M. Taylor, Where the really hard problems are, in: Proc. of IJCAI-91, Vol. 1, 1991, pp. 331\u2013337.","journal-title":"Proc. of IJCAI-91"},{"key":"5119363_CR11","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann and D. Loveland, A machine program for theorem-proving, Communications of the ACM 5 (1962) 394\u2013397.","journal-title":"Communications of the ACM"},{"key":"5119363_CR12","series-title":"Technical Report","volume-title":"Backtracking algorithms for constraint satisfaction problems","author":"R. Dechter","year":"1999","unstructured":"R. Dechter and D. Frost, Backtracking algorithms for constraint satisfaction problems, Technical Report, Information and Computer Science Department, UC Irvine (1999); http:\/\/www.ics.uci.edu\/~csp\/r56-backtracking.pdf."},{"key":"5119363_CR13","unstructured":"O. Dubois, Y. Boufkhad and J. Mandler, Typical random 3-SAT formulae and the satisfiability threshold, in: Symposium on Discrete Algorithms, 2000."},{"key":"5119363_CR14","unstructured":"D. Estrin et al., Instrumenting the world with wireless sensor networks, in: Proc. of International Conference on Acoustics, Speech and Signal Processing (ICASSP 2001), 2001."},{"key":"5119363_CR15","unstructured":"D. Estrin et al., Embedded, everywhere: A research agenda for networked systems of embedded computers, National Research Council Report (2001)."},{"issue":"4","key":"5119363_CR16","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"E. Friedgut, Sharp thresholds of graph proprties, and the k-SAT problem, J. Amer. Math. Soc. 12(4) (1999) 1017\u20131054.","journal-title":"J. Amer. Math. Soc."},{"key":"5119363_CR17","doi-asserted-by":"crossref","first-page":"2993","DOI":"10.1090\/S0002-9939-96-03732-X","volume":"124","author":"E. Friedgut","year":"1996","unstructured":"E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996) 2993\u20133002.","journal-title":"Proc. Amer. Math. Soc."},{"key":"5119363_CR18","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A.M. Frieze","year":"1996","unstructured":"[18] [Frieze and Suen] A.M. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms 20 (1996) 312\u2013355.","journal-title":"Journal of Algorithms"},{"key":"5119363_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979)."},{"key":"5119363_CR20","first-page":"547","volume-title":"Stochastic Analysis, Control, Optimization and Applications","author":"P. Gupta","year":"1998","unstructured":"P. Gupta and P.R. Kumar, Critical power for asymptotic connectivity in wireless networks, in: Stochastic Analysis, Control, Optimization and Applications, eds. W.M. McEneany et al. (Birkh\u00e4user, Boston, MA, 1998) pp. 547\u2013566."},{"issue":"8","key":"5119363_CR21","volume":"17","year":"1999","unstructured":"Z.J. Haas et al., eds., IEEE Journal on Selected Areas in Communications 17(8) (1999). Special Issue on Wireless Ad Hoc Networks.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"issue":"12","key":"5119363_CR22","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"W.K. Hale, Frequency assignment: theory and applications, Proceedings of the IEEE 68(12) (1980) 1497\u20131514.","journal-title":"Proceedings of the IEEE"},{"key":"5119363_CR23","unstructured":"Y. Hamadi, C. Bessi\u00e8re and J. Quinqueton, Backtracking in distributed constraint networks, in: Proceedings of the 13th European Conference on Artificial Intelligence (ECAI-98), 1998, pp. 219\u2013223."},{"key":"5119363_CR24","unstructured":"D. Hochbaum, Approximation Algorithms for NP-Hard Problems (Brooks\/Cole, 1996)."},{"issue":"5163","key":"5119363_CR25","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions, Science 264(5163) (1994) 1297\u20131301.","journal-title":"Science"},{"key":"5119363_CR26","unstructured":"B. Krishnamachari, Phase transitions, structure, and complexity in wireless networks, Ph.D. Thesis, Cornell University (2002)."},{"key":"5119363_CR27","unstructured":"B. Krishnamachari, R. Bejar and S.B.Wicker, Distributed problem solving and the boundaries of selfconfiguration in multi-hop wireless networks, in: Proc. of 35th Hawaii International Conference on System Sciences, 2002."},{"key":"5119363_CR28","unstructured":"B. Krishnamachari et al., Critical density thresholds in distributed wireless networks, a chapter for book in honor of Ian Blake (to appear). Available online at http:\/\/www.krishnamachari.net\/papers\/densityChapter.pdf."},{"key":"5119363_CR29","unstructured":"B. Krishnamachari, S.B. Wicker and R. Bejar, Phase transitions in wireless ad-hoc networks, in: Proc. of IEEE GlobeCom 2001, 2001."},{"key":"5119363_CR30","volume-title":"Wireless Networks and Mobile Computing Handbook","author":"E.L. Lloyd","year":"2001","unstructured":"E.L. Lloyd, Broadcast scheduling for tdma in wireless multi-hop networks, in: Wireless Networks and Mobile Computing Handbook, ed. I. Stojmenovic (Wiley, New York, 2001)."},{"key":"5119363_CR31","volume-title":"Distributed Algorithms","author":"N.A. Lynch","year":"1996","unstructured":"N.A. Lynch, Distributed Algorithms (Morgan Kauffman, San Mateo, CA, 1996)."},{"key":"5119363_CR32","doi-asserted-by":"crossref","unstructured":"R. Meester and R. Roy, Continuum Percolation (Cambridge Univ. Press, 1996).","DOI":"10.1017\/CBO9780511895357"},{"key":"5119363_CR33","volume-title":"How to Solve It: Modern Heuristics","author":"Z. Michalewicz","year":"1999","unstructured":"Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics (Springer, Berlin, 1999)."},{"key":"5119363_CR34","unstructured":"D. Mitchell, B. Selman and H. Levesque, Hard and easy distributions of SAT problems, in: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Jose, CA, 1992, pp. 459\u2013465."},{"key":"5119363_CR35","volume-title":"Ad Hoc Networking","author":"C. Perkins","year":"2002","unstructured":"C. Perkins, Ad Hoc Networking (Addison-Wesley, Reading, MA, 2002)."},{"key":"5119363_CR36","doi-asserted-by":"crossref","unstructured":"L.C. Pond and V.O.K. Li, A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks, in: Proc of MILCOM, 1989, pp. 70\u201374.","DOI":"10.1109\/MILCOM.1989.103901"},{"key":"5119363_CR37","doi-asserted-by":"crossref","unstructured":"R. Ramaswami and K.K. Parhi, Distributed scheduling of broadcasts in a radio network, in: Proc. of INFOCOM, 1989, pp. 497\u2013504.","DOI":"10.1109\/INFCOM.1989.101493"},{"key":"5119363_CR38","doi-asserted-by":"crossref","unstructured":"M. Sanchez, P. Manzoni and Z.J. Haas, Determination of critical transmission range in ad-hoc networks, in: Multiaccess Mobility and Teletraffic for Wireless Communications Workshop (MMT'99), 1999.","DOI":"10.1007\/978-1-4757-5920-4_30"},{"key":"5119363_CR39","doi-asserted-by":"crossref","unstructured":"M. Seddigh, J.S. Gonzales and I. Stojmenovic, RNG and internal node based broadcasting algorithms for wireless one-to-one networks, ACM Mobile Computing and Communications Review 5(2) (2001).","DOI":"10.1145\/584066.584069"},{"key":"5119363_CR40","unstructured":"B. Selman, H.A. Kautz and B. Cohen, Noise strategies for improving local search, in: Proc. of the National Conference for Artificial Intelligence (AAAI'94), 1994."},{"issue":"5","key":"5119363_CR41","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/98.878532","volume":"7","author":"K. Sohrabi","year":"2000","unstructured":"K. Sohrabi et al., Protocols for self-organization of a wireless sensor network, IEEE Personal Communications 7(5) (2000) 16\u201327.","journal-title":"IEEE Personal Communications"},{"key":"5119363_CR42","volume-title":"Ad Hoc Mobile Wireless Networks: Protocols and Systems","author":"C.K. Toh","year":"2001","unstructured":"C.K. Toh, Ad Hoc Mobile Wireless Networks: Protocols and Systems (Prentice-Hall, Englewood Cliffs, NJ, 2001)."},{"key":"5119363_CR43","unstructured":"B. Vandegriend, Finding Hamiltonian cycles: algorithms, graphs and performance, Masters Thesis, Department of Computer Science, University of Alberta, Canada. Available online with source code for algorithms at http:\/\/www.cs.ualberta.ca\/?basil\/research.html."},{"key":"5119363_CR44","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C.P. Williams","year":"1994","unstructured":"C.P. Williams and T. Hogg, Exploiting the deep structure of constraint problems, Artificial Intelligence 70 (1994) 73\u2013117.","journal-title":"Artificial Intelligence"},{"key":"5119363_CR45","doi-asserted-by":"crossref","unstructured":"Y. Xu, J. Heidemann and D. Estrin, Geography-informed energy conservation for ad hoc routing, in: Proc. of the Seventh Annual ACM\/IEEE International Conference on Mobile Computing and Networking (ACM MobiCom), 2001.","DOI":"10.1145\/381677.381685"},{"key":"5119363_CR46","unstructured":"[Xue and Kumar] F. Xue and P.R. Kumar, The number of neighbors needed for connectivity of wireless networks (2002, submitted)."},{"issue":"5","key":"5119363_CR47","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1109\/69.729707","volume":"10","author":"M. Yokoo","year":"1998","unstructured":"M. Yokoo et al., The distributed constraint satisfaction problem: formalization and algorithms, IEEE Transactions on Knowledge and Data Engineering 10(5) (1998) 673\u2013685.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"}],"container-title":["Telecommunication Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023426501170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1023426501170\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1023426501170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T06:49:20Z","timestamp":1754635760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1023426501170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":47,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["5119363"],"URL":"https:\/\/doi.org\/10.1023\/a:1023426501170","relation":{},"ISSN":["1018-4864","1572-9451"],"issn-type":[{"type":"print","value":"1018-4864"},{"type":"electronic","value":"1572-9451"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}