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

The modular decomposition of a graph $G=(V,E)$ does not contain prime modulesif and only if $G$ is a cograph, that is, if no quadruple of vertices induces asimple connected path $P_4$. The cograph editing problem consists in insertinginto and deleting from $G$ a set $F$ of edges so that $H=(V,E\Delta F)$ is acograph and $|F|$ is minimum. This NP-hard combinatorial optimization problemhas recently found applications, e.g., in the context of phylogenetics.Efficient heuristics are hence of practical importance. The simplecharacterization of cographs in terms of their modular decomposition suggeststhat instead of editing $G$ one could operate directly on the modulardecomposition. We show here that editing the induced $P_4$s is equivalent toresolving prime modules by means of a suitable defined merge operation on thesubmodules. Moreover, we characterize so-called module-preserving edit sets anddemonstrate that optimal pairwise sequences of module-preserving edit setsexist for every non-cograph. This eventually leads to an exact algorithm forthe cograph editing problem as well as fixed-parameter tractable (FPT) resultswhen cograph editing is parameterized by the so-called modular-width. Inaddition, we provide two heuristics with time complexity $O(|V|^3)$, resp.,$O(|V|^2)$.

Cograph Editing: Merging Modules is equivalent to Editing P4's