The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1, \ldots, w_{|V(G)|} \in \Sigma$ and a so-called decoder $D \subseteq \Sigma^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i<j \le |V(G)|, w_iw_j \in D\})$. It took around two decad...
Henning Fernau, S. German, Kevin Mann et al.· 1 citation
Here, the most natural parameters such as the budgets d and a of the players, the vertex cover number and treewidth of the input graph, and combinations of these parameters are considered, showing that the encoding of the costs and weights of the edges has a considerable influence on the problem complexity.
Christian Komusiewicz, Zhenwei Liu, Nils Morawietz et al.· International Workshop on Gr...· 0 citations
