An Efficient and Robust  Distributed Vertex Coloring  Algorithm  in  Wireless Networks

An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks Mohammadhasan Miri, Ali Ahmadian, Sayed A. Hadei This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4651070/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract The distributed vertex coloring is one of the most intensively studied problem in graph theory with many applications in computer networks.We propose a deterministic distributed algorithm for this problem in wireless networks.The algorithm's run-time is divided into rounds.In each round, every uncolored vertex or at least one of its neighbors obtains a color equal to the round number and informs its neighbors of the taken color with a 1-bit message. Therefore, the bit complexity is minimum. Moreover, the set of colored vertices is a maximal independent set (MIS), and the maximum number of colors or rounds equals the maximum number of MISs that cover the graph's vertices. It is bounded by the maximum vertex degree and also the radius of the graph.This is the first algorithm that uses a lower bound on the number of colors for every graph.In the case of trees, the logarithm of the number of vertices is another upper bound for it. Finally, we propose another algorithm for 2-coloring, and the number of rounds is bounded by the diameter of the tree. Bit complexity collision maximal independent set time complexity vertex coloring problem wireless networks Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4651070","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":320049615,"identity":"ad8f2e29-26a7-442f-aa29-e16b6a0b4271","order_by":0,"name":"Mohammadhasan Miri","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAArUlEQVRIiWNgGAWjYDACCSBOYJCQQ+ISqcWYRC1AkNhAtLt0Zzewbni4xyJ9fkQC44cfDBb5BLWY3TnAdiPhmUTuxhsJzJI9DBKWBK0zu5EA1HIAqGVGAoM00J0GhG2Bakk3nJHA/JskLQnyEglsxNqS2AbSYriB52GbZY8BUVqSj938caBOXr49+fCNHxV1hLUwMDA2gCmDAyAGMRrgQL6BFNWjYBSMglEwogAAKRk4UVUwAQIAAAAASUVORK5CYII=","orcid":"","institution":"Golstan University","correspondingAuthor":true,"prefix":"","firstName":"Mohammadhasan","middleName":"","lastName":"Miri","suffix":""},{"id":320049616,"identity":"ab2bcf79-93bf-4f8c-887d-cd9de834b8ac","order_by":1,"name":"Ali Ahmadian","email":"","orcid":"","institution":"Sharif University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Ali","middleName":"","lastName":"Ahmadian","suffix":""},{"id":320049617,"identity":"bfed8eb8-79ff-4278-925c-730d402229fb","order_by":2,"name":"Sayed A. Hadei","email":"","orcid":"","institution":"Tarbiat Modares University","correspondingAuthor":false,"prefix":"","firstName":"Sayed","middleName":"A.","lastName":"Hadei","suffix":""}],"badges":[],"createdAt":"2024-06-27 22:38:16","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4651070/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4651070/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":60908678,"identity":"a30c18e1-caa9-4694-8695-8f656723538b","added_by":"auto","created_at":"2024-07-23 12:29:22","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":421556,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4651070/v1_covered_93852bb4-f114-4367-85b1-641d6fed0e2d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Bit complexity, collision, maximal independent set, time complexity, vertex coloring problem, wireless networks","lastPublishedDoi":"10.21203/rs.3.rs-4651070/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4651070/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"The distributed vertex coloring is one of the most intensively studied problem in graph theory with many applications in computer networks.We propose a deterministic distributed algorithm for this problem in wireless networks.The algorithm's run-time is divided into rounds.In each round, every uncolored vertex or at least one of its neighbors obtains a color equal to the round number and informs its neighbors of the taken color with a 1-bit message. Therefore, the bit complexity is minimum. Moreover, the set of colored vertices is a maximal independent set (MIS), and the maximum number of colors or rounds equals the maximum number of MISs that cover the graph's vertices. It is bounded by the maximum vertex degree and also the radius of the graph.This is the first algorithm that uses a lower bound on the number of colors for every graph.In the case of trees, the logarithm of the number of vertices is another upper bound for it. Finally, we propose another algorithm for 2-coloring, and the number of rounds is bounded by the diameter of the tree.","manuscriptTitle":"An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-22 17:19:40","doi":"10.21203/rs.3.rs-4651070/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"30339dd4-29fb-4d1b-8a33-5be05a4bc21f","owner":[],"postedDate":"July 22nd, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-07-23T12:21:14+00:00","versionOfRecord":[],"versionCreatedAt":"2024-07-22 17:19:40","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4651070","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4651070","identity":"rs-4651070","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}