Acceso al sitio web del Consejo de Políticas de Infraestructura
REVISTA
Algorithms

   
Redirigiendo al acceso original de articulo en 16 segundos...
Inicio  /  Algorithms  /  Vol: 14 Par: 4 (2021)  /  Artículo
ARTÍCULO
TITULO

Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs

David Schaller    
Manuela Geiß    
Marc Hellmuth and Peter F. Stadler    

Resumen

Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.

PÁGINAS
pp. 0 - 0

 Artículos similares

       
 
Jiahuan Lin, Huawei Duan, Baoming Xu, Yangwei Wang and Jun Zhang    
The Froude-scaled offshore floating wind turbine model is inevitably affected by the Reynolds number effect, making the model unable to correctly reproduce the thrust performance of the reference wind turbine (RWT). To solve this problem, an Xfoil-Airfoi... ver más

 
Kelin Luo and Frits C. R. Spieksma    
Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are giv... ver más
Revista: Algorithms

 
Youri Geurkink, Jan Boone, Steven Verstockt and Jan G. Bourgois    
This study aimed to identify the strongest predictive variables of winning and losing in the highest Belgian soccer division. A predictive machine learning model based on a broad range of variables (n = 100) was constructed, using a dataset consisting of... ver más
Revista: Applied Sciences

 
Birger Hjørland    
Information retrieval (IR) is about making systems for finding documents or information. Knowledge organization (KO) is the field concerned with indexing, classification, and representing documents for IR, browsing, and related processes, whether perform... ver más
Revista: Information

 
Qinglian Hou, Cheng Zhou, Rong Wan, Junbo Zhang and Feng Xue    
Tuna fish school detection provides information on the fishing decisions of purse seine fleets. Here, we present a recognition system that included fish shoal image acquisition, point extraction, point matching, and data storage. Points are a crucial cha... ver más