A QUBO formulation for the tree containment problem

DOI10.1016/J.TCS.2022.09.012MaRDI QIDQ2699952zbMATH OpenOpenAlexFDO

Authors Michael J. Dinneen, Pankaj S. Ghodla, Simone Linz

Publication date 20 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic trees and networksquantum computingQUBOstree containment

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Locating a tree in a phylogenetic network
• Solving the tree containment problem for genetically stable networks in quadratic time
• Embedding phylogenetic trees in networks of low treewidth
• Tree containment with soft polytomies
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks

Cites work

• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Advances in unconventional computing. Volume 1. Theory
• Complexity of uniqueness and local search in quadratic 0-1 programming
• Counting phylogenetic networks
• Displaying trees across two phylogenetic networks
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Locating a tree in a phylogenetic network
• On determining if tree-based networks contain fixed trees
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• Quantum theory, the Church–Turing principle and the universal quantum computer
• QUBO formulations for the graph isomorphism problem and related problems
• Reticulation-visible networks
• Seeing the trees and their branches in the network is hard

This page was built for publication: A QUBO formulation for the tree containment problem

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