  Finding cohesive subgraphs in a large graph has many important applications,
such as community detection and biological network analysis. Clique is often a
too strict cohesive structure since communities or biological modules rarely
form as cliques for various reasons such as data noise. Therefore, $k$-plex is
introduced as a popular clique relaxation, which is a graph where every vertex
is adjacent to all but at most $k$ vertices. In this paper, we propose a fast
branch-and-bound algorithm as well as its task-based parallel version to
enumerate all maximal $k$-plexes with at least $q$ vertices. Our algorithm
adopts an effective search space partitioning approach that provides a lower
time complexity, a new pivot vertex selection method that reduces candidate
vertex size, an effective upper-bounding technique to prune useless branches,
and three novel pruning techniques by vertex pairs. Our parallel algorithm uses
a timeout mechanism to eliminate straggler tasks, and maximizes cache locality
while ensuring load balancing. Extensive experiments show that compared with
the state-of-the-art algorithms, our sequential and parallel algorithms
enumerate large maximal $k$-plexes with up to $5 \times$ and $18.9 \times$
speedup, respectively. Ablation results also demonstrate that our pruning
techniques bring up to $7 \times$ speedup compared with our basic algorithm.
