Name
Abstract | ||
|---|---|---|
The modular decomposition of a graph $G=(V,E)$ does not contain prime modules if and only if $G$ is a cograph, that is, if no quadruple of vertices induces a simple connected path $P_4$. The cograph editing problem consists in inserting into and deleting from $G$ a set $F$ of edges so that $H=(V,EDelta F)$ is a cograph and $|F|$ is minimum. This NP-hard combinatorial optimization problem has recently found applications, e.g., in the context of phylogenetics. Efficient heuristics are hence of practical importance. The simple characterization of cographs in terms of their modular decomposition suggests that instead of editing $G$ one could operate directly on the modular decomposition. We show here that editing the induced $P_4$s is equivalent to resolving prime modules by means of a suitable defined merge operation on the submodules. Moreover, we characterize so-called module-preserving edit sets and demonstrate that optimal pairwise sequences of module-preserving edit sets exist for every non-cograph. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Discrete Mathematics | Prime (order theory),Pairwise comparison,Graph,Discrete mathematics,Combinatorics,Modular decomposition,Vertex (geometry),Heuristics,Cograph,Merge (version control),Mathematics |
DocType | Volume | Citations |
Journal | abs/1702.07499 | 0 |
PageRank | References | Authors |
0.34 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| marc hellmuth | 1 | 148 | 22.80 |
| Adrian Fritz | 2 | 2 | 1.20 |
| Nicolas Wieseke | 3 | 114 | 9.34 |
| Peter F. Stadler | 4 | 256 | 62.77 |