A branch and bound irredundant graph algorithm for large-scale MLCS problems
作者：
Highlights：
• Design a branch and bound strategy for identifying non-contributed points and non-longest paths.
• Construct a much smaller DAG than those constructed by the existing algorithms.
• Design a strategy for deleting points in the Hash table timely.
• Propose a new data structure for storing Small-DAG to avoid topological sorting.
• Propose a new algorithm for larger-scale MLCS problems with lower time and space cost.
摘要
•Design a branch and bound strategy for identifying non-contributed points and non-longest paths.•Construct a much smaller DAG than those constructed by the existing algorithms.•Design a strategy for deleting points in the Hash table timely.•Propose a new data structure for storing Small-DAG to avoid topological sorting.•Propose a new algorithm for larger-scale MLCS problems with lower time and space cost.
论文关键词：Multiple longest common subsequences,Small DAG,Branch and bound,Gene alignment
论文评审过程：Received 14 November 2020, Revised 6 April 2021, Accepted 18 May 2021, Available online 28 May 2021, Version of Record 11 June 2021.
论文官网地址：https://doi.org/10.1016/j.patcog.2021.108059
