BROWSE

Related Scientist

kevin,hendrey's photo.

kevin,hendrey
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Twin-width of random graphs

DC Field Value Language
dc.contributor.authorAhn, Jungho-
dc.contributor.authorChakraborti, Debsoumya-
dc.contributor.authorKevin Hendrey-
dc.contributor.authorDonggyu Kim-
dc.contributor.authorSang-il Oum-
dc.date.accessioned2024-12-12T07:00:54Z-
dc.date.available2024-12-12T07:00:54Z-
dc.date.created2024-06-24-
dc.date.issued2024-12-
dc.identifier.issn1042-9832-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/15554-
dc.description.abstractWe investigate the twin-width of the Erdos-Renyi random graph G n,p). We unveil a surprising behavior of this parameter by showing the existence of a constant p & lowast;approximate to 0.4such that with high probability, when p & lowast;<= p <= 1-p & lowast;,the twin-width is asymptotically 2p(1-p)n, whereas, when0<p<p & lowast;or 1>p>1-p & lowast;, the twin-width is significantly higher than 2p(1-p)n. In addition, we show that the twin-width of G(n,1/2)is concentrated aroundn/2-root 3nlogn/2 within an interval of length o(root n log n).For the sparse random graph, we show that with high probability, the twin-width of G(n,p) is Theta (n root p) when (726 ln n)/ n <= p <= 1/2-
dc.language영어-
dc.publisherJohn Wiley & Sons Inc.-
dc.titleTwin-width of random graphs-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid001248187800001-
dc.identifier.scopusid2-s2.0-85196109476-
dc.identifier.rimsid83329-
dc.contributor.affiliatedAuthorKevin Hendrey-
dc.contributor.affiliatedAuthorDonggyu Kim-
dc.contributor.affiliatedAuthorSang-il Oum-
dc.identifier.doi10.1002/rsa.21247-
dc.identifier.bibliographicCitationRandom Structures and Algorithms, v.65, no.4, pp.794 - 831-
dc.relation.isPartOfRandom Structures and Algorithms-
dc.citation.titleRandom Structures and Algorithms-
dc.citation.volume65-
dc.citation.number4-
dc.citation.startPage794-
dc.citation.endPage831-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalWebOfScienceCategoryComputer Science, Software Engineering-
dc.relation.journalWebOfScienceCategoryMathematics, Applied-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordAuthorrandom graph-
dc.subject.keywordAuthorthreshold-
dc.subject.keywordAuthortwin-width-
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Data Science Group(데이터 사이언스 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse