Abstrakt. År 2000 publicerade T. Uno och M. Yagiura en algoritm som beräknar alla K gemensamma intervall av två givna permutationer av längd n i O(n + K) tid. Vårt papper presenterar först en nedbrytning strategi för att få en kompakt kodning för gemensamma intervall av d permutationer. Sedan går vi igenom T. Uno och M. Yagiuras algoritm för att ge en linjär tidsalgoritm för att hitta denna kodning. Dessutom anpassar vi algoritmen för att få en linjär modulär nedbrytning av en oriktad graf och föreslår därmed ett formellt invariantbaserat bevis för alla dessa algoritmer.
REF nådde en linjär tidsalgoritm inom ramen för definitionen av PQ-träd.
Revisiting T. Uno and M. Yagiura’s algorithm
{'venue': 'Proc. 16th International Symposium on Algorithms and Computation, in Lecture Notes in Comput. Sci', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}