Parameterized algorithms for the Steiner arborescence problem on a hypercube

DOI10.1007/S00236-024-00474-8MaRDI QIDQ6659999zbMATH OpenFDO

Authors Sugyani Mahapatra, Manikandan Narayanan, N. S. Narayanaswamy

Publication date 10 January 2025

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00236-024-00474-8

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• Near optimal bounds for Steiner trees in the hypercube
• Dynamic programming for minimum Steiner trees
• A Polynomial-Time Algorithm for Near-Perfect Phylogeny
• scientific article; zbMATH DE number 2102787

Cites work

• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Additive approximation for near-perfect phylogeny construction
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7788470 (Why is no real title available?)
• On the approximability of the Steiner tree problem in phylogeny
• Parameterized algorithms
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Polylogarithmic inapproximability
• Research in Computational Molecular Biology
• Research in Computational Molecular Biology
• The computational complexity of inferring rooted phylogenies by parsimony
• The steiner problem in graphs
• The Steiner problem in phylogeny is NP-complete
• Two variations of the minimum Steiner problem

This page was built for publication: Parameterized algorithms for the Steiner arborescence problem on a hypercube

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