English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Tree representations of (sets of) symmetric binary relations, or equivalentlyedge-colored undirected graphs, are of central interest, e.g.\ inphylogenomics. In this context symbolic ultrametrics play a crucial role.Symbolic ultrametrics define an edge-colored complete graph that allows torepresent the topology of this graph as a vertex-colored tree. Here, we areinterested in the structure and the complexity of certain combinatorialproblems resulting from considerations based on symbolic ultrametrics, and onalgorithms to solve them.  This includes, the characterization of symbolic ultrametrics thatadditionally distinguishes between edges and non-edges of \emph{arbitrary}edge-colored graphs $G$ and thus, yielding a tree representation of $G$, bymeans of so-called cographs. Moreover, we address the problem of finding"closest" symbolic ultrametrics and show the NP-completeness of the threeproblems: symbolic ultrametric editing, completion and deletion. Finally, asnot all graphs are cographs, and hence, don't have a tree representation, weask, furthermore, what is the minimum number of cotrees needed to represent thetopology of an arbitrary non-cograph $G$. This is equivalent to find an optimalcograph edge $k$-decomposition $\{E_1,\dots,E_k\}$ of $E$ so that each subgraph$(V,E_i)$ of $G$ is a cograph. We investigate this problem in full detail,resulting in several new open problems, and NP-hardness results.  For all optimization problems proven to be NP-hard we will provide integerlinear program (ILP) formulations to efficiently solve them.

On Tree Representations of Relations and Graphs: Symbolic Ultrametrics and Cograph Edge Decompositions