  $k$-clique listing is a vital graph mining operator with diverse applications
in various networks. The state-of-the-art algorithms all adopt a
branch-and-bound (BB) framework with a vertex-oriented branching strategy
(called VBBkC), which forms a sub-branch by expanding a partial $k$-clique with
a vertex. These algorithms have the time complexity of $O(k m
(\delta/2)^{k-2})$, where $m$ is the number of edges in the graph and $\delta$
is the degeneracy of the graph. In this paper, we propose a BB framework with a
new edge-oriented branching (called EBBkC), which forms a sub-branch by
expanding a partial $k$-clique with two vertices that connect each other (which
correspond to an edge). We explore various edge orderings for EBBkC such that
it achieves a time complexity of $O(\delta m + k m (\tau/2)^{k-2})$, where
$\tau$ is an integer related to the maximum truss number of the graph and we
have $\tau < \delta$. The time complexity of EBBkC is better than that of VBBkC
algorithms for $k>3$ since both $O(\delta m)$ and $O(k m (\tau/2)^{k-2})$ are
bounded by $O(k m (\delta/2)^{k-2})$. Furthermore, we develop specialized
algorithms for sub-branches on dense graphs so that we can early-terminate them
and apply the specialized algorithms. We conduct extensive experiments on 19
real graphs, and the results show that our newly developed EBBkC-based
algorithms with the early termination technique consistently and largely
outperform the state-of-the-art (VBBkC-based) algorithms.
