  We consider problems that can be formulated as a task of finding an optimal
triangulation of a graph w.r.t. some notion of optimality. We present
algorithms parameterized by the size of a minimum edge clique cover ($cc$) to
such problems. This parameterization occurs naturally in many problems in this
setting, e.g., in the perfect phylogeny problem $cc$ is at most the number of
taxa, in fractional hypertreewidth $cc$ is at most the number of hyperedges,
and in treewidth of Bayesian networks $cc$ is at most the number of non-root
nodes.
  We show that the number of minimal separators of graphs is at most $2^{cc}$,
the number of potential maximal cliques is at most $3^{cc}$, and these objects
can be listed in times $O^*(2^{cc})$ and $O^*(3^{cc})$, respectively, even when
no edge clique cover is given as input; the $O^*(\cdot)$ notation omits factors
polynomial in the input size. These enumeration algorithms imply $O^*(3^{cc})$
time algorithms for problems such as treewidth, weighted minimum fill-in, and
feedback vertex set. For generalized and fractional hypertreewidth we give
$O^*(4^m)$ time and $O^*(3^m)$ time algorithms, respectively, where $m$ is the
number of hyperedges. When an edge clique cover of size $cc'$ is given as a
part of the input we give $O^*(2^{cc'})$ time algorithms for treewidth, minimum
fill-in, and chordal sandwich. This implies an $O^*(2^n)$ time algorithm for
perfect phylogeny, where $n$ is the number of taxa. We also give polynomial
space algorithms with time complexities $O^*(9^{cc'})$ and $O^*(9^{cc +
O(\log^2 cc)})$ for problems in this framework.
