Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs
- Title
- Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs
- Authors
- OH, EUNJIN; Oh, Seunghyeok
- Date Issued
- 2023-09-05
- Publisher
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
- 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 on a hyperbolic random graph G in O(m+n
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/119827
- Article Type
- Conference
- Citation
- 31st Annual European Symposium on Algorithms, ESA 2023, 2023-09-05
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.