Rotationsavståndet mellan träden mäter antalet enkla åtgärder som krävs för att förvandla ett träd till ett annat. Det finns inga kända polynom-tidsalgoritmer för beräkning av rotationsavstånd. När det gäller beställda rotade träd visar vi att rotationsavståndet mellan två beställda träd är fastparameterdragbart, i parametern k, rotationsavståndet. Beviset bygger på kernaliseringen av de ursprungliga träden till träd med en storlek som begränsas av 7k.
Nyligen visade det sig att problemet är fast parameter kan dras i flip avstånd REF.
Rotation Distance is Fixed-Parameter Tractable
{'venue': 'Inform. Process. Lett. 109 (2009), no. 16, 918-922', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}