{"id":"https://openalex.org/W2051491278","doi":"https://doi.org/10.1002/dac.726","title":"A new distributed approximation algorithm for constructing minimum connected dominating set in wireless <i>ad hoc</i> networks","display_name":"A new distributed approximation algorithm for constructing minimum connected dominating set in wireless <i>ad hoc</i> networks","publication_year":2005,"publication_date":"2005-03-15","ids":{"openalex":"https://openalex.org/W2051491278","doi":"https://doi.org/10.1002/dac.726","mag":"2051491278"},"language":"en","primary_location":{"id":"doi:10.1002/dac.726","is_oa":true,"landing_page_url":"https://doi.org/10.1002/dac.726","pdf_url":"https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/dac.726","source":{"id":"https://openalex.org/S175310385","display_name":"International Journal of Communication Systems","issn_l":"1074-5351","issn":["1074-5351","1099-1131"],"is_oa":false,"is_in_doaj":false,"is_core":true,"host_organization":"https://openalex.org/P4310320595","host_organization_name":"Wiley","host_organization_lineage":["https://openalex.org/P4310320595"],"host_organization_lineage_names":["Wiley"],"type":"journal"},"license":null,"license_id":null,"version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"International Journal of Communication Systems","raw_type":"journal-article"},"type":"article","indexed_in":["crossref"],"open_access":{"is_oa":true,"oa_status":"bronze","oa_url":"https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/dac.726","any_repository_has_fulltext":false},"authorships":[{"author_position":"first","author":{"id":"https://openalex.org/A5034847404","display_name":"Bo Gao","orcid":"https://orcid.org/0000-0002-7405-7507"},"institutions":[{"id":"https://openalex.org/I183067930","display_name":"Shanghai Jiao Tong University","ror":"https://ror.org/0220qvk04","country_code":"CN","type":"education","lineage":["https://openalex.org/I183067930"]}],"countries":["CN"],"is_corresponding":true,"raw_author_name":"Bo Gao","raw_affiliation_strings":["Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200030, China","Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200030,China)"],"affiliations":[{"raw_affiliation_string":"Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200030, China","institution_ids":["https://openalex.org/I183067930"]},{"raw_affiliation_string":"Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200030,China)","institution_ids":["https://openalex.org/I183067930"]}]},{"author_position":"middle","author":{"id":"https://openalex.org/A5101771561","display_name":"Yuhang Yang","orcid":"https://orcid.org/0000-0001-9530-301X"},"institutions":[{"id":"https://openalex.org/I183067930","display_name":"Shanghai Jiao Tong University","ror":"https://ror.org/0220qvk04","country_code":"CN","type":"education","lineage":["https://openalex.org/I183067930"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Yuhang Yang","raw_affiliation_strings":["Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200030, China","Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200030,China)"],"affiliations":[{"raw_affiliation_string":"Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200030, China","institution_ids":["https://openalex.org/I183067930"]},{"raw_affiliation_string":"Department of Electronic Engineering,Shanghai Jiao Tong University,Shanghai 200030,China)","institution_ids":["https://openalex.org/I183067930"]}]},{"author_position":"last","author":{"id":"https://openalex.org/A5100294037","display_name":"Huiye Ma","orcid":null},"institutions":[{"id":"https://openalex.org/I177725633","display_name":"Chinese University of Hong Kong","ror":"https://ror.org/00t33hh48","country_code":"CN","type":"education","lineage":["https://openalex.org/I177725633"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Huiye Ma","raw_affiliation_strings":["Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, China","[Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, China]"],"affiliations":[{"raw_affiliation_string":"Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, China","institution_ids":["https://openalex.org/I177725633"]},{"raw_affiliation_string":"[Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, China]","institution_ids":["https://openalex.org/I177725633"]}]}],"institutions":[],"countries_distinct_count":1,"institutions_distinct_count":3,"corresponding_author_ids":["https://openalex.org/A5034847404"],"corresponding_institution_ids":["https://openalex.org/I183067930"],"apc_list":{"value":3450,"currency":"USD","value_usd":3450},"apc_paid":null,"fwci":2.0764,"has_fulltext":false,"cited_by_count":32,"citation_normalized_percentile":{"value":0.88733357,"is_in_top_1_percent":false,"is_in_top_10_percent":false},"cited_by_percentile_year":{"min":89,"max":96},"biblio":{"volume":"18","issue":"8","first_page":"743","last_page":"762"},"is_retracted":false,"is_paratext":false,"is_xpac":false,"primary_topic":{"id":"https://openalex.org/T10246","display_name":"Mobile Ad Hoc Networks","score":0.9998999834060669,"subfield":{"id":"https://openalex.org/subfields/1705","display_name":"Computer Networks and Communications"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},"topics":[{"id":"https://openalex.org/T10246","display_name":"Mobile Ad Hoc Networks","score":0.9998999834060669,"subfield":{"id":"https://openalex.org/subfields/1705","display_name":"Computer Networks and Communications"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T10796","display_name":"Cooperative Communication and Network Coding","score":0.9983999729156494,"subfield":{"id":"https://openalex.org/subfields/1705","display_name":"Computer Networks and Communications"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T10720","display_name":"Complexity and Algorithms in Graphs","score":0.9943000078201294,"subfield":{"id":"https://openalex.org/subfields/1703","display_name":"Computational Theory and Mathematics"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}}],"keywords":[{"id":"https://openalex.org/keywords/connected-dominating-set","display_name":"Connected dominating set","score":0.8869585990905762},{"id":"https://openalex.org/keywords/computer-science","display_name":"Computer science","score":0.7607591152191162},{"id":"https://openalex.org/keywords/wireless-ad-hoc-network","display_name":"Wireless ad hoc network","score":0.7392540574073792},{"id":"https://openalex.org/keywords/approximation-algorithm","display_name":"Approximation algorithm","score":0.6645628213882446},{"id":"https://openalex.org/keywords/dominating-set","display_name":"Dominating set","score":0.6547608375549316},{"id":"https://openalex.org/keywords/algorithm","display_name":"Algorithm","score":0.6165679097175598},{"id":"https://openalex.org/keywords/vertex","display_name":"Vertex (graph theory)","score":0.5639694929122925},{"id":"https://openalex.org/keywords/maximal-independent-set","display_name":"Maximal independent set","score":0.525169312953949},{"id":"https://openalex.org/keywords/distributed-algorithm","display_name":"Distributed algorithm","score":0.5175396800041199},{"id":"https://openalex.org/keywords/computational-complexity-theory","display_name":"Computational complexity theory","score":0.43038487434387207},{"id":"https://openalex.org/keywords/time-complexity","display_name":"Time complexity","score":0.43029695749282837},{"id":"https://openalex.org/keywords/wireless-network","display_name":"Wireless network","score":0.42571714520454407},{"id":"https://openalex.org/keywords/graph","display_name":"Graph","score":0.40821295976638794},{"id":"https://openalex.org/keywords/wireless","display_name":"Wireless","score":0.37860897183418274},{"id":"https://openalex.org/keywords/theoretical-computer-science","display_name":"Theoretical computer science","score":0.31416523456573486},{"id":"https://openalex.org/keywords/distributed-computing","display_name":"Distributed computing","score":0.22811266779899597},{"id":"https://openalex.org/keywords/line-graph","display_name":"Line graph","score":0.08435755968093872}],"concepts":[{"id":"https://openalex.org/C37810922","wikidata":"https://www.wikidata.org/wiki/Q5161409","display_name":"Connected dominating set","level":3,"score":0.8869585990905762},{"id":"https://openalex.org/C41008148","wikidata":"https://www.wikidata.org/wiki/Q21198","display_name":"Computer science","level":0,"score":0.7607591152191162},{"id":"https://openalex.org/C94523657","wikidata":"https://www.wikidata.org/wiki/Q4085781","display_name":"Wireless ad hoc network","level":3,"score":0.7392540574073792},{"id":"https://openalex.org/C148764684","wikidata":"https://www.wikidata.org/wiki/Q621751","display_name":"Approximation algorithm","level":2,"score":0.6645628213882446},{"id":"https://openalex.org/C146661039","wikidata":"https://www.wikidata.org/wiki/Q2915204","display_name":"Dominating set","level":4,"score":0.6547608375549316},{"id":"https://openalex.org/C11413529","wikidata":"https://www.wikidata.org/wiki/Q8366","display_name":"Algorithm","level":1,"score":0.6165679097175598},{"id":"https://openalex.org/C80899671","wikidata":"https://www.wikidata.org/wiki/Q1304193","display_name":"Vertex (graph theory)","level":3,"score":0.5639694929122925},{"id":"https://openalex.org/C18359143","wikidata":"https://www.wikidata.org/wiki/Q7888149","display_name":"Maximal independent set","level":5,"score":0.525169312953949},{"id":"https://openalex.org/C130120984","wikidata":"https://www.wikidata.org/wiki/Q2835898","display_name":"Distributed algorithm","level":2,"score":0.5175396800041199},{"id":"https://openalex.org/C179799912","wikidata":"https://www.wikidata.org/wiki/Q205084","display_name":"Computational complexity theory","level":2,"score":0.43038487434387207},{"id":"https://openalex.org/C311688","wikidata":"https://www.wikidata.org/wiki/Q2393193","display_name":"Time complexity","level":2,"score":0.43029695749282837},{"id":"https://openalex.org/C108037233","wikidata":"https://www.wikidata.org/wiki/Q11375","display_name":"Wireless network","level":3,"score":0.42571714520454407},{"id":"https://openalex.org/C132525143","wikidata":"https://www.wikidata.org/wiki/Q141488","display_name":"Graph","level":2,"score":0.40821295976638794},{"id":"https://openalex.org/C555944384","wikidata":"https://www.wikidata.org/wiki/Q249","display_name":"Wireless","level":2,"score":0.37860897183418274},{"id":"https://openalex.org/C80444323","wikidata":"https://www.wikidata.org/wiki/Q2878974","display_name":"Theoretical computer science","level":1,"score":0.31416523456573486},{"id":"https://openalex.org/C120314980","wikidata":"https://www.wikidata.org/wiki/Q180634","display_name":"Distributed computing","level":1,"score":0.22811266779899597},{"id":"https://openalex.org/C203776342","wikidata":"https://www.wikidata.org/wiki/Q1378376","display_name":"Line graph","level":3,"score":0.08435755968093872},{"id":"https://openalex.org/C76155785","wikidata":"https://www.wikidata.org/wiki/Q418","display_name":"Telecommunications","level":1,"score":0.0},{"id":"https://openalex.org/C43517604","wikidata":"https://www.wikidata.org/wiki/Q7144893","display_name":"Pathwidth","level":4,"score":0.0}],"mesh":[],"locations_count":1,"locations":[{"id":"doi:10.1002/dac.726","is_oa":true,"landing_page_url":"https://doi.org/10.1002/dac.726","pdf_url":"https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/dac.726","source":{"id":"https://openalex.org/S175310385","display_name":"International Journal of Communication Systems","issn_l":"1074-5351","issn":["1074-5351","1099-1131"],"is_oa":false,"is_in_doaj":false,"is_core":true,"host_organization":"https://openalex.org/P4310320595","host_organization_name":"Wiley","host_organization_lineage":["https://openalex.org/P4310320595"],"host_organization_lineage_names":["Wiley"],"type":"journal"},"license":null,"license_id":null,"version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"International Journal of Communication Systems","raw_type":"journal-article"}],"best_oa_location":{"id":"doi:10.1002/dac.726","is_oa":true,"landing_page_url":"https://doi.org/10.1002/dac.726","pdf_url":"https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/dac.726","source":{"id":"https://openalex.org/S175310385","display_name":"International Journal of Communication Systems","issn_l":"1074-5351","issn":["1074-5351","1099-1131"],"is_oa":false,"is_in_doaj":false,"is_core":true,"host_organization":"https://openalex.org/P4310320595","host_organization_name":"Wiley","host_organization_lineage":["https://openalex.org/P4310320595"],"host_organization_lineage_names":["Wiley"],"type":"journal"},"license":null,"license_id":null,"version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"International Journal of Communication Systems","raw_type":"journal-article"},"sustainable_development_goals":[{"display_name":"No poverty","id":"https://metadata.un.org/sdg/1","score":0.4300000071525574}],"awards":[],"funders":[],"has_content":{"pdf":true,"grobid_xml":false},"content_urls":{"pdf":"https://content.openalex.org/works/W2051491278.pdf"},"referenced_works_count":15,"referenced_works":["https://openalex.org/W10935558","https://openalex.org/W1983502795","https://openalex.org/W2011039300","https://openalex.org/W2018438786","https://openalex.org/W2045349136","https://openalex.org/W2063572899","https://openalex.org/W2098502330","https://openalex.org/W2108986762","https://openalex.org/W2120170057","https://openalex.org/W2139349113","https://openalex.org/W2143022286","https://openalex.org/W2145797586","https://openalex.org/W2169848785","https://openalex.org/W3141863997","https://openalex.org/W4285719527"],"related_works":["https://openalex.org/W2952723382","https://openalex.org/W4301177232","https://openalex.org/W1483891445","https://openalex.org/W2388345276","https://openalex.org/W2155984879","https://openalex.org/W1530712874","https://openalex.org/W3047117384","https://openalex.org/W2206986926","https://openalex.org/W4242849573","https://openalex.org/W2007607373"],"abstract_inverted_index":{"Abstract":[0],"In":[1,28,109,159],"recent":[2],"years,":[3],"constructing":[4],"a":[5,11,30,48,56,62,74,97,114,121,130,142],"virtual":[6],"backbone":[7],"by":[8],"nodes":[9],"in":[10,37,42,50,78,88,211],"connected":[12,63,69],"dominating":[13,31,57,70],"set":[14,32,44,58,71,133],"(CDS)":[15],"has":[16,141,223],"been":[17,86],"proposed":[18,87],"to":[19,47,204],"improve":[20],"the":[21,38,43,51,67,89,166,212],"performance":[22,194,227],"of":[23,92,168],"ad":[24,125],"hoc":[25,126],"wireless":[26,124],"networks.":[27],"general,":[29],"satisfies":[33],"that":[34,59,119,182,220],"every":[35],"vertex":[36,49],"graph":[39,79],"is":[40,55,73,138,174],"either":[41],"or":[45],"adjacent":[46],"set.":[52],"A":[53],"CDS":[54],"also":[60,200],"induces":[61],"sub\u2010graph.":[64],"However,":[65],"finding":[66],"minimum":[68],"(MCDS)":[72],"well\u2010known":[75],"NP\u2010hard":[76],"problem":[77],"theory.":[80],"Approximation":[81],"algorithms":[82,94,210],"for":[83,123,196],"MCDS":[84,122],"have":[85],"literature.":[90,213],"Most":[91],"these":[93],"suffer":[95],"from":[96,102],"poor":[98],"approximation":[99,117,144],"ratio,":[100,145],"and":[101,106,146,152,172,216,226],"high":[103],"time":[104,151],"complexity":[105],"message":[107,157],"complexity.":[108,158],"this":[110,160],"paper,":[111],"we":[112],"present":[113],"new":[115],"distributed":[116],"algorithm":[118,207,222],"constructs":[120],"networks":[127],"based":[128],"on":[129],"maximal":[131],"independent":[132],"(MIS).":[134],"Our":[135],"algorithm,":[136,161,198],"which":[137],"fully":[139],"localized,":[140],"constant":[143],"O":[147,153],"(":[148,154],"n":[149,155],")":[150,156],"each":[162],"node":[163],"only":[164,175,191],"requires":[165],"knowledge":[167],"its":[169],"one\u2010hop":[170],"neighbours":[171],"there":[173],"one":[176],"shortest":[177],"path":[178],"connecting":[179],"two":[180],"dominators":[181],"are":[183],"at":[184],"most":[185],"three":[186],"hops":[187],"away.":[188],"We":[189],"not":[190],"give":[192],"theoretical":[193,217],"analysis":[195,218],"our":[197,206,221],"but":[199],"conduct":[201],"extensive":[202],"simulation":[203],"compare":[205],"with":[208],"other":[209],"Simulation":[214],"results":[215],"show":[219],"better":[224],"efficiency":[225],"than":[228],"others.":[229],"Copyright":[230],"\u00a9":[231],"2005":[232],"John":[233],"Wiley":[234],"&amp;":[235],"Sons,":[236],"Ltd.":[237]},"counts_by_year":[{"year":2024,"cited_by_count":1},{"year":2022,"cited_by_count":1},{"year":2021,"cited_by_count":1},{"year":2020,"cited_by_count":2},{"year":2019,"cited_by_count":1},{"year":2017,"cited_by_count":2},{"year":2016,"cited_by_count":1},{"year":2015,"cited_by_count":1},{"year":2013,"cited_by_count":1},{"year":2012,"cited_by_count":2}],"updated_date":"2025-11-06T03:46:38.306776","created_date":"2025-10-10T00:00:00"}