DC Field | Value | Language |
---|---|---|
dc.contributor.author | 오승혁 | - |
dc.date.accessioned | 2023-08-31T16:36:06Z | - |
dc.date.available | 2023-08-31T16:36:06Z | - |
dc.date.issued | 2023 | - |
dc.identifier.other | OAK-2015-10257 | - |
dc.identifier.uri | http://postech.dcollection.net/common/orgView/200000690252 | ko_KR |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/118454 | - |
dc.description | Master | - |
dc.description.abstract | In this paper, we study the maximum clique problem on hyperbolic random graphs. A hyperbolic random graph is a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. We propose a simple algorithm for finding a maximum clique in hyperbolic random graph. We first analyze the running time of our algorithm theoretically. We can compute a maximum clique in $O(m + n^{4.5(1-\alpha)})$ expected time if the geometric representation of the hyperbolic random graph is given or in $O(m + n^{6(1-\alpha)})$ expected time if the geometric representation is not given. Also, we implemented and evaluated our algorithm empirically. Our algorithm outperforms the previous algorithm [BFK18] practically and theoretically. Beyond the hyperbolic random graphs, we have experiment on real-world networks. For most of instances, we get large cliques close to the optimum solutions efficiently. | - |
dc.language | eng | - |
dc.publisher | 포항공과대학교 | - |
dc.title | Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs | - |
dc.title.alternative | 하이퍼볼릭 랜덤 그래프에서 최대 클리크를 계산하기 위한 알고리즘 | - |
dc.type | Thesis | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.date.degree | 2023- 8 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.