On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions

DOI10.1007/978-3-319-21398-9_48zbMath1468.05227arXiv1501.03931OpenAlexW1849163561MaRDI QIDQ3196420

Nicolas Wieseke, Marc Hellmuth

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.03931

zbMATH Keywords

NP-completenesscographedge partitionsymbolic ultrametriccotree

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Beyond representing orthology relations by trees ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Inferring phylogenetic trees from the knowledge of rare evolutionary events ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ Representing graphs as the intersection of cographs and threshold graphs ⋮ From modular decomposition trees to rooted median graphs ⋮ Forbidden time travel: Characterization of time-consistent tree reconciliation maps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity and parameterized algorithms for cograph editing
• Complement reducible graphs
• A constructive proof of Vizing's theorem
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• The complexity of \(G\)-free colourability
• Finite automata and pattern avoidance in words
• Words restricted by patterns with at most 2 distinct letters
• Orthology relations, symbolic ultrametrics, and cographs
• Vertex Partitions of Graphs into Cographs and Stars
• Cograph Editing: Complexity and Parameterized Algorithms
• Enumeration of some classes of words avoiding two generalized patterns of length three
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• A Note on the Superlinear Convergence of GMRES
• The complexity of satisfiability problems