Katriel och Bodlaender [7] ändrar algoritmen som föreslagits av Alpern et al. [2] för att upprätthålla den topologiska ordningen av n noderna i en riktad acyklisk graf samtidigt infoga m-kanter och bevisa att deras algoritm körs i O(min {m 3/2 log n, m 3/2 + n 2 log n}) tid och har en (m 3/2 ) lägre gräns. I det här dokumentet ger vi en snäv analys av deras algoritm genom att visa att den körs i tid (m 3/2 + mn 1/2 log n) 1.
I REF bevisade vi att Katriel-Bodlaender-algoritmen tar tid för att infoga m-kanter (m 3/2 + mn 1/2 log n).
A Tight Analysis of the Katriel-Bodlaender Algorithm for Online Topological Ordering
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}