On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions

DOI10.1007/s10878-017-0111-7zbMath1402.90147arXiv1509.05069OpenAlexW2964289968MaRDI QIDQ721942

Nicolas Wieseke, Marc Hellmuth

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeeditingcographedge partitioninteger linear program (ILP)symbolic ultrametric

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Complete edge-colored permutation graphs ⋮ Best match graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ From modular decomposition trees to rooted median graphs

Uses Software

• Proteinortho

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
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Vertex Partitions of Graphs into Cographs and Stars
• Cograph Editing: Complexity and Parameterized Algorithms
• On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
• Enumeration of some classes of words avoiding two generalized patterns of length three
• A Linear Recognition Algorithm for Cographs
• The complexity of some edge deletion problems
• Graph Classes: A Survey
• The complexity of satisfiability problems