Fitch graph completion

DOI10.1007/978-3-031-49193-1_17MaRDI QIDQ6591635

Sandhya Thekkumpadan Puthiyaveedu, Peter F. Stadler, Marc Hellmuth

Publication date: 22 August 2024

zbMATH Keywords

NP-completerecognition algorithmhorizontal gene transferFitch graphdirected cograph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

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

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)