Ett grundläggande problem i beräkningsbiologin är den fylogeniska rekonstruktionen för en uppsättning specifika organismer. Ett av grafens teoretiska tillvägagångssätt är att konstruera en likhetsdiagram på den uppsättning organismer där adjacensen indikerar evolutionär närhet, och sedan att rekonstruera en fylogeni genom att beräkna ett träd som förbinder organismerna så att bladen i trädet är märkta av organismerna och varje organism visas som ett blad i trädet. Likhetsdiagrammet är enkelt och oriktat. För varje par av angränsande organismer i likhetsdiagrammet ska deras avstånd i utgångsträdet, som mäts med antalet kanter på den väg som förbinder dem, vara mindre än någon förspecificerad gräns. Detta är känt som problemet med att känna igen blad krafter och dator blad rötter. Grafer som är blad krafter är kända för att vara ackord. Det visas i detta papper att alla strikt ackord grafer är blad befogenheter och en linjär tid algoritm presenteras för att beräkna en bladrot för någon given strikt ackord diagram. Ett mellanliggande rot-och-kraft-problem, Steiner-rotproblemet, undersöks också.
De gav en linjär tid algoritm för att konstruera k-blad rötter av strikt ackord diagram REF.
Strictly chordal graphs are leaf powers
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}