{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T22:41:56Z","timestamp":1778539316921,"version":"3.51.4"},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,4]]},"abstract":"<jats:p> A maximal independent set (MIS) S for a graph G is an independent set and no proper superset of S is also independent. A set S is dominating if each node in the graph is either in S or adjacent to one of the nodes in S. The subgraph weakly induced by S is the graph G\u2032 such that each edge in G\u2032 has at least one end point in S. A set S is a weakly-connected dominating set (WCDS) of G if S is dominating and G\u2032 is connected. G\u2032 is a sparse spanner if it has linear edges. The nodes of WCDS have been proposed in the literature as clusterheads for clustered wireless ad hoc networks. In this paper, we present two distributed algorithms for constructing a WCDS for wireless ad hoc networks in linear time. The first algorithm has an approximation ratio of 5, and requires O(n log n) messages, while the second algorithm has a larger approximation ratio, and requires only O(n) messages. Both of these algorithms are used to obtain sparse spanners. The spanner obtained by the second algorithm has a topological dilation of 3, and a geometric dilation of 6. Both of these algorithms are based on the construction of a MIS. The first algorithm requires the construction of a spanning tree. The second algorithm is fully localized, and does not depend on the spanning tree, which makes the maintenance of the WCDS simpler, and guarantees the maintenance of the same approximation ratio. <\/jats:p>","DOI":"10.1142\/s012905410300173x","type":"journal-article","created":{"date-parts":[[2003,6,19]],"date-time":"2003-06-19T08:43:20Z","timestamp":1056012200000},"page":"287-303","source":"Crossref","is-referenced-by-count":59,"title":["MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS"],"prefix":"10.1142","volume":"14","author":[{"given":"KHALED M.","family":"ALZOUBI","sequence":"first","affiliation":[{"name":"Department of Computer Science, Illinois Institute of Technology, 10 West 31st Street, Chicago, Illinois 60616, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PENG-JUN","family":"WAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Illinois Institute of Technology, 10 West 31st Street, Chicago, Illinois 60616, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OPHIR","family":"FRIEDER","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Illinois Institute of Technology, 10 West 31st Street, Chicago, Illinois 60616, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","author":"Alzoubi K. M.","journal-title":"ACM Journal of MONET"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/JCN.2002.6596929"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00233-6"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1145\/584066.584069"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410300173X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:39:21Z","timestamp":1565138361000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410300173X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":7,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,4]]}},"alternative-id":["10.1142\/S012905410300173X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410300173x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}