Fitch graph completion

DOI10.1007/978-3-031-49193-1_17MaRDI QIDQ6591635zbMATH OpenFDO

Authors Marc Hellmuth, Peter F. Stadler, Sandhya Thekkumpadan Puthiyaveedu

Publication date 22 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49193-1_17

zbMATH Keywords

NP-completerecognition algorithmhorizontal gene transferFitch graphdirected cograph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A Linear Recognition Algorithm for Cographs
• Alternative characterizations of Fitch's xenology relation
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Complement reducible graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Linear-time modular decomposition of directed graphs
• Partial homology relations -- satisfiability in terms of di-cographs
• Reconstructing gene trees from Fitch's xenology relation
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Reducibility among combinatorial problems
• Topological sorting of large networks

This page was built for publication: Fitch graph completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6591635)