Abstrakt. En av de viktigaste uppsättningarna i samband med en poset P är dess uppsättning linjära förlängningar, E(P ). I detta dokument presenterar vi en algoritm för att generera alla linjära förlängningar av en poset i konstant avkortad tid; det vill säga, i tiden O(e(P )), där e(P ) = jE(P )j. Den snabbaste tidigare kända algoritmen för att generera linjära förlängningar av en poset körs i tid O(n e(P )), där n är antalet element i poset. Vår algoritm är den rst konstanta amortized tid algoritm för att generera en \naturligt de ned" klass av kombinatoriska objekt för vilka motsvarande räkna problem är #P-komplett. Dessutom visar vi att linjära förlängningar kan genereras i konstant amorterad tid där varje förlängning dier från sin föregångare genom en eller två intilliggande införlivanden. Algoritmen är praktisk och kan modifieras för att eektivt räkna linjära förlängningar, och för att beräkna P (x < y), för alla par x; y, i tiden O(n 2 + e(P )).
En algoritm som genererar alla linjära förlängningar av en poset i konstant amortized tid, det vill säga i tid O( och L(P) ), presenterades av Pruesse och Ruskey REF.
Generating Linear Extensions Fast
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}