2018 · 37 citations · 15 references
ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresCombinatorial OptimizationGraph AlgorithmsGraph AnalyticsGraph MiningGraph SimplificationGraph TheoryClique AlgorithmsClique StructureCliquesComputational Complexity Of Graph AlgorithmsScalable Graph Algorithms
The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.
15
Fast maximum clique algorithms for large graphs
Ryan A. Rossi, David F. Gleich, Assefaw H. Gebremedhin et al. · 2014 · 103 citations