För en oriktad n-vertex graf G med icke-negativa kant-vikter, anser vi följande typ av fråga: med tanke på två hörn s och t i G, vad är vikten av en minsta st-skuren i G? Vi löser detta problem i förbehandlingstiden O(n log 3 n) för grafer av avgränsat släkte, vilket ger den första sub-kvadratiska tid algoritm för denna klass av grafer. Vårt resultat förbättras också genom en logaritmisk faktor en tidigare algoritm av Borradaile, Sankowski och Wulff-Nilsen (FOCS 2010) som endast tillämpas på plana grafer. Vår algoritm konstruerar ett Gomory-Hu-träd för den givna grafen, vilket ger en datastruktur med utrymme O(n) som kan svara på minimala cut-frågor i konstant tid. Beroendet av släktet av ingångsgrafen i vår förbehandlingstid är 2 O(g 2 ).
Borradaile m.fl. REF gav en O(n log 3 n) algoritm för att bearbeta en begränsad-genus graf och konstruera en datastruktur som stöder konstant-tid s-t minsta skär frågor.
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs