On minimum vertex bisection of random d-regular graphs

dc.authorscopusid 7401603758
dc.authorscopusid 55630908700
dc.authorscopusid 56211714900
dc.authorscopusid 59141878800
dc.contributor.author Yaşar Diner, Öznur
dc.contributor.author Diner, Oznur Yasar
dc.contributor.author Serna, Maria
dc.contributor.author Serra, Oriol
dc.contributor.other Computer Engineering
dc.date.accessioned 2024-06-23T21:36:48Z
dc.date.available 2024-06-23T21:36:48Z
dc.date.issued 2024
dc.department Kadir Has University en_US
dc.department-temp [Serna, Maria] Barcelona TECH, Comp Sci Dept, ALBCOM Res Grp, Univ Politecn Catalunya, Barcelona, Spain; [Diner, Oznur Yasar] Kadir Has Univ, Comp Engn Dept, Istanbul, Turkiye; [Diaz, Josep; Diner, Oznur Yasar; Serra, Oriol] Barcelona TECH, Math Dept, Univ Politecn Catalunya, Barcelona, Spain; [Diaz, Josep; Serna, Maria; Serra, Oriol] Barcelona TECH, Inst Matemat, Univ Politecn Catalunya, Barcelona, Spain en_US
dc.description.abstract Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d -regular graphs, for constant values of d . Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non -trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/). en_US
dc.description.sponsorship Spanish Agencia Estatal de Investigacion [PID2020-13082GB-I00, PID2020-112581GB-C21]; Scientific and Technological Research Council Tuebitak [BIDEB 2219-1059B191802095]; Kadir Has University [2018-BAP-08] en_US
dc.description.sponsorship J. Diaz and M. Serna were partially supported by the Spanish Agencia Estatal de Investigacion under project MOTION, PID2020-112581GB-C21. O.Y. Diner was partially supported by the Scientific and Technological Research Council Tuebitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra research was supported by the Spanish Agencia Estatal de Investigacion under project CONTREWA, PID2020-13082GB-I00. en_US
dc.identifier.citationcount 0
dc.identifier.doi 10.1016/j.jcss.2024.103550
dc.identifier.issn 0022-0000
dc.identifier.issn 1090-2724
dc.identifier.scopus 2-s2.0-85194072135
dc.identifier.scopusquality Q1
dc.identifier.uri https://doi.org/10.1016/j.jcss.2024.103550
dc.identifier.uri https://hdl.handle.net/20.500.12469/5643
dc.identifier.volume 144 en_US
dc.identifier.wos WOS:001247310900002
dc.identifier.wosquality Q3
dc.language.iso en en_US
dc.publisher Academic Press inc Elsevier Science en_US
dc.relation.publicationcategory Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı en_US
dc.rights info:eu-repo/semantics/openAccess en_US
dc.scopus.citedbyCount 0
dc.subject Vertex bisection number en_US
dc.subject Random regular graphs en_US
dc.subject Differential equations method en_US
dc.title On minimum vertex bisection of random d-regular graphs en_US
dc.type Article en_US
dc.wos.citedbyCount 0
dspace.entity.type Publication
relation.isAuthorOfPublication 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isAuthorOfPublication.latestForDiscovery 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isOrgUnitOfPublication fd8e65fe-c3b3-4435-9682-6cccb638779c
relation.isOrgUnitOfPublication.latestForDiscovery fd8e65fe-c3b3-4435-9682-6cccb638779c

Files