  In this work, we study two natural generalizations of clique-width introduced
by Martin F\"urer. Multi-clique-width (mcw) allows every vertex to hold
multiple labels [ITCS 2017], while for fusion-width (fw) we have a possibility
to merge all vertices of a certain label [LATIN 2014]. F\"urer has shown that
both parameters are upper-bounded by treewidth thus making them more appealing
from an algorithmic perspective than clique-width and asked for applications of
these parameters for problem solving. First, we determine the relation between
these two parameters by showing that $\operatorname{mcw} \leq \operatorname{fw}
+ 1$. Then we show that when parameterized by multi-clique-width, many problems
(e.g., Connected Dominating Set) admit algorithms with the same running time as
for clique-width despite the exponential gap between these two parameters. For
some problems (e.g., Hamiltonian Cycle) we show an analogous result for
fusion-width: For this we present an alternative view on fusion-width by
introducing so-called glue-expressions which might be interesting on their own.
All algorithms obtained in this work are tight up to (Strong) Exponential Time
Hypothesis.
