Cograph editing: Merging modules is equivalent to editing P_4s
From MaRDI portal
Publication:5121555
DOI10.26493/2590-9770.1252.e71zbMath1441.05195arXiv1702.07499OpenAlexW3013530612MaRDI QIDQ5121555
Peter F. Stadler, Marc Hellmuth, Nicolas Wieseke, Adrian Fritz
Publication date: 15 September 2020
Published in: The Art of Discrete and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.07499
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Taxonomy, cladistics, statistics in mathematical biology (92B10) Structural characterization of families of graphs (05C75)
Related Items (5)
Linear-time minimal cograph editing ⋮ Complete characterization of incorrect orthology assignments in best match graphs ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Indirect identification of horizontal gene transfer ⋮ From modular decomposition trees to rooted median graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The cluster deletion problem for cographs
- A survey of the algorithmic aspects of modular decomposition
- Complexity and parameterized algorithms for cograph editing
- On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
- On the X-join decomposition for undirected graphs
- Complement reducible graphs
- On minimal augmentation of a graph to obtain an interval graph
- Recovering symbolically dated, rooted trees from symbolic ultrametrics
- Modular decomposition and transitive orientation
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
- Reconstructing gene trees from Fitch's xenology relation
- Partial homology relations -- satisfiability in terms of di-cographs
- Orthology relations, symbolic ultrametrics, and cographs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- Applying modular decomposition to parameterized cluster editing problems
- Reciprocal best match graphs
- Best match graphs
- On a property of the class of n-colorable graphs
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- Parameterized Algorithms for Modular-Width
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Cograph Editing: Complexity and Parameterized Algorithms
- On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- Graphs with unique maximal clumpings
- Graph Classes: A Survey
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
- Orthology Relation and Gene Tree Correction: Complexity Results
- Algorithm Theory - SWAT 2004
- Transitiv orientierbare Graphen
- Complexity classification of some edge modification problems
This page was built for publication: Cograph editing: Merging modules is equivalent to editing P_4s
