Algorithms · 2013 · 43 citations · 17 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGraph AlgorithmsParallel Performance AnalysisScalable Algorithm DesignClique AlgorithmsCliquesComputational Complexity Of Graph AlgorithmsParallel AdaptationParallel Graph AlgorithmsParallel Graph Data StructuresScalable Graph Algorithms
We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.
17
John L. Gustafson · Communications of the ACM · 1988 · 1.4K citations · Full text
Where the really hard problems are
Peter Cheeseman, Bob Kanefsky, William M. Taylor · 1991 · 1K citations