Priority-Based Genetic Algorithm for theClustered Steiner Tree Problem

Priority-Based Genetic Algorithm for theClustered Steiner Tree Problem | 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 Priority-Based Genetic Algorithm for theClustered Steiner Tree Problem Tuan-Anh Do, Ha-Bang Ban, Minh Tu Le, Duc Hung Phan, Thai Ha Nguyen, and 1 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3507907/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 In a complex network connecting many devices, a set of nodes might be partitioned into multiple local clusters with different functions, properties, or communication protocols. Thus, there has been a rise in network design problems with additional constraints regarding the clustering of vertices, one of them being the Clustered Steiner Tree Problem - a variant of the Steiner Tree Problem. In the literature, there have been a few research working on this problem, but either they only solve it in a metric case, or their exploration capability is still limited. Therefore, their results are not actually good in many cases. To overcome the drawbacks, we propose a Priority-Based Genetic Algorithm to solve the Clustered Steiner Tree Problem. The proposed algorithm maintains a balance between exploration and exploitation to prevent the search from local optima. Experiments and comparisons to existing works in non-metric and metric cases are carried out deliberately to prove the remarkable performance of the proposed algorithm. Genetic Algorithm Clustered Steiner Tree Problem 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-3507907","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":243902303,"identity":"cac23fcc-f75e-4924-b790-2807d2799031","order_by":0,"name":"Tuan-Anh Do","email":"","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Tuan-Anh","middleName":"","lastName":"Do","suffix":""},{"id":243902304,"identity":"31c07710-2de4-4e4e-9d17-1abb88d1fbbe","order_by":1,"name":"Ha-Bang Ban","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABAUlEQVRIiWNgGAWjYBACAyBmZmywAZJAFmMDRFSCCC1pIC2MDSAtPERqOcwAtoMoLebsZw+/Ltxx3p6fnfn5A8Ydh+3tGZgP3uZhOJyHS4tlT16a9cwztxNnNrMZNjCeOZzYw8CWbA3UUozTYQdyzIx5224nGBzmATqs7XACDwOPmTQPQ1piAy4t59+AtJyzh2mx52Hg/4Zfy40c48e8bQcYN0C1MPYw8LABtdjg1GI5440Z88y2ZLBfZiS2pSf2HGYztpxjgFuLOX+O8efCNjt7fv7DDz58bLO2Z29vfnjjTYUETi1AwIaIhQQQwQx2MG71ICUf8EqPglEwCkbBKAAA8+VRlCA2+lMAAAAASUVORK5CYII=","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Ha-Bang","middleName":"","lastName":"Ban","suffix":""},{"id":243902305,"identity":"dc30dd4f-6154-4e15-a280-9ea58ccc198e","order_by":2,"name":"Minh Tu Le","email":"","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Minh","middleName":"Tu","lastName":"Le","suffix":""},{"id":243902306,"identity":"269015d9-9f96-4e41-a1d0-6c85e1f090c3","order_by":3,"name":"Duc Hung Phan","email":"","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Duc","middleName":"Hung","lastName":"Phan","suffix":""},{"id":243902307,"identity":"488ca148-4f7c-4dce-b8f3-19e3bb52949d","order_by":4,"name":"Thai Ha Nguyen","email":"","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Thai","middleName":"Ha","lastName":"Nguyen","suffix":""},{"id":243902308,"identity":"e9c5030d-284d-46dd-87a8-84ec5599ab5c","order_by":5,"name":"Thi Thanh Binh Huynh","email":"","orcid":"","institution":"Hanoi University of Science and Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Thi","middleName":"Thanh Binh","lastName":"Huynh","suffix":""}],"badges":[],"createdAt":"2023-10-29 16:14:12","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3507907/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3507907/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":47402930,"identity":"08594cd7-bf9e-4ee9-8492-46a61b911e97","added_by":"auto","created_at":"2023-11-30 21:52:24","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":866174,"visible":true,"origin":"","legend":"","description":"","filename":"PBGAfortheCluSteiner.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3507907/v1_covered_b20dbb97-210e-48fa-b5e1-22cb51b6bdff.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Priority-Based Genetic Algorithm for theClustered Steiner Tree Problem","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":"Genetic Algorithm, Clustered Steiner Tree Problem","lastPublishedDoi":"10.21203/rs.3.rs-3507907/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3507907/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"In a complex network connecting many devices, a set of nodes might be partitioned into multiple local clusters with different functions, properties, or communication protocols. Thus, there has been a rise in network design problems with additional constraints regarding the clustering of vertices, one of them being the Clustered Steiner Tree Problem - a variant of the Steiner Tree Problem. In the literature, there have been a few research working on this problem, but either they only solve it in a metric case, or their exploration capability is still limited. Therefore, their results are not actually good in many cases. To overcome the drawbacks, we propose a Priority-Based Genetic Algorithm to solve the Clustered Steiner Tree Problem. The proposed algorithm maintains a balance between exploration and exploitation to prevent the search from local optima. Experiments and comparisons to existing works in non-metric and metric cases are carried out deliberately to prove the remarkable performance of the proposed algorithm.","manuscriptTitle":"Priority-Based Genetic Algorithm for theClustered Steiner Tree Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2023-10-31 06:45:17","doi":"10.21203/rs.3.rs-3507907/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":"21da1706-8b0e-41e9-96ad-097a3c82ee6b","owner":[],"postedDate":"October 31st, 2023","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-04-16T06:02:42+00:00","versionOfRecord":[],"versionCreatedAt":"2023-10-31 06:45:17","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-3507907","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3507907","identity":"rs-3507907","version":["v1"]},"buildId":"7rjqhiLT3MXkJMwkYKINL","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}