Page 435 - 《软件学报》2024年第6期

徐兰天 等: 面向超图数据的最大独立集算法 3011

[doi: 10.1023/A:1016747704458]
[7] Lee G, Ko J, Shin K. Hypergraph motifs: Concepts, algorithms, and discoveries. Proc. of the VLDB Endowment, 2020, 13(12):
2256–2269. [doi: 10.14778/3407790.3407823]
[8] Yoon SE, Song H, Shin K, Yi Y. How much and when do we need higher-order information in hypergraphs? A case study on hyperedge
prediction. In: Proc. of the 2020 Web Conf. Taipei: ACM, 2020. 2627–2633. [doi: 10.1145/3366423.3380016]
[9] Kook Y, Ko J, Shin K. Evolution of real-world hypergraphs: Patterns and models without oracles. In: Proc. of the 2020 IEEE Int’l Conf.
on Data Mining (ICDM). Sorrento: IEEE, 2020. 272–281. [doi: 10.1109/ICDM50108.2020.00036]
[10] Benson AR, Abebe R, Schaub MT, Jadbabaie A, Kleinberg J. Simplicial closure and higher-order link prediction. Proc.of the National
Academy of Sciences of the United States of America, 2018, 115(48): E11221–E11230. [doi: 10.1073/pnas.1800683115]
[11] Finocchi I, Finocchi M, Fusco EG. Clique counting in mapreduce: Algorithms and experiments. ACM Journal of Experimental
Algorithmics, 2015, 20: 1–20. [doi: 10.1145/2794080]
[12] Hu XC, Tao FY, Chung CW. I/o-efficient algorithms on triangle listing and counting. ACM Trans. on Database Systems, 2014, 39(4): 27.
[doi: 10.1145/2691190.2691193]
[13] Estrada E, Rodríguez-Velázquez JA. Subgraph centrality and clustering in complex hyper-networks. Physica A: Statistical Mechanics and
its Applications, 2006, 364: 581–594. [doi: 10.1016/j.physa.2005.12.002]
2012, 196(1): 611–634. [doi: 10.1007/s10479-012-1124-3]
[14] Gregori E, Lenzini L, Mainardi S. Parallel k-clique community detection on large-scale networks. IEEE Trans. on Parallel and Distributed
Systems, 2013, 24(8): 1651–1660. [doi: 10.1109/TPDS.2012.229]
[15] Do MT, Yoon SE, Hooi B, Shin K. Structural patterns and generative models of real-world hypergraphs. In: Proc. of the 26th ACM
SIGKDD Int’l Conf. on Knowledge Discovery & Data Mining. Virtual Event: ACM, 2020. 176–186. [doi: 10.1145/3394486.3403060]
[16] Benson AR, Kumar R, Tomkins A. Sequences of sets. In: Proc. of the 24th ACM SIGKDD Int’l Conf. on Knowledge Discovery & Data
Mining. London: ACM, 2018. 1148–1157. [doi: 10.1145/3219819.3220100]
[17] Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young JG, Petri G. Networks beyond pairwise interactions: Structure
and dynamics. Physics Reports, 2020, 874: 1–92. [doi: 10.1016/j.physrep.2020.05.004]
[18] Carraghan R, Pardalos PM. An exact algorithm for the maximum clique problem. Operations Research Letters, 1990, 9(6): 375–382. [doi:
10.1016/0167-6377(90)90057-C]
[19] Pardalos PM, Rodgers GP. A branch and bound algorithm for the maximum clique problem. Computers & Operations Research, 1992,
19(5): 363–375. [doi: 10.1016/0305-0548(92)90067-F]
[20] Östergård PRJ. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 2002, 120(1–3): 197–207. [doi: 10.
1016/S0166-218X(01)00290-6]
[21] Li CM, Quan Z. An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. Proc. of the AAAI Conf. on
Artificial Intelligence, 2010, 24(1): 128–133. [doi: 10.1609/aaai.v24i1.7536]
[22] Xiao MY, Nagamochi H. Exact algorithms for maximum independent set. Information and Computation, 2017, 255: 126–146. [doi: 10.
1016/j.ic.2017.06.001]
[23] Akiba T, Iwata Y. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoretical Computer
Science, 2016, 609: 211–225. [doi: 10.1016/j.tcs.2015.09.023]
[24] Karp RM. Reducibility among combinatorial problems. In: Proc. of the 1972 Symp. on the Complexity of Computer Computations. New
York: Plenum Press, 1972. 85–103. [doi: 10.1007/978-1-4684-2001-2_9]
[25] Jagota A, Sanchis LA. Adaptive, restart, randomized greedy heuristics for maximum clique. Journal of Heuristics, 2001, 7(6): 565–585.
[doi: 10.1023/A:1011925109392]
[26] Pullan W. Phased local search for the maximum clique problem. Journal of Combinatorial Optimization, 2006, 12(3): 303–323. [doi: 10.
1007/s10878-006-9635-y]
[27] Wu QH, Hao JK, Glover F. Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research,

[28] Zhou XD, Wang LA, Chen L. Research on using heuristic algorithms to solve MCP. Computer Engineering and Design, 2007, 28(18):
4329–4332 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-7024.2007.18.002]
[29] Feng Y. A heuristic algorithm for maximum independent set problem in graph theory. Journal of the Hebei Academy of Sciences, 2021,
38(3): 9–13 (in Chinese with English abstract). [doi: 10.16191/j.cnki.hbkx.2021.03.002]
[30] Liu Y, Lu J, Yang H, Xiao XK, Wei ZW. Towards maximum independent sets on massive graphs. Proc. of the VLDB Endowment, 2015,
8(13): 2122–2133. [doi: 10.14778/2831360.2831366]
[31] Lamm S, Sanders P, Schulz C, Strash D, Werneck RF. Finding near-optimal independent sets at scale. In: Proc. of the 2016 Meeting on