Vi visar att den exakta beräkningen av ett minimum eller en maximal skärning av en given graf G är utom räckhåll för alla en-pass streaming algoritm, det vill säga för alla algoritmer som kör över ingångsströmmen av G's kanter bara en gång och har ett arbetsminne av o(n 2 ) bitar. Detta gäller även om randomisering är tillåten.
Zelke visar att alla algoritmer som kan hitta en minsta skärning av en oriktad graf kräver Vðm på bitar av arbetsminnet, detta förblir sant även om randomisering tillåts REF.
Intractability of min- and max-cut in streaming graphs
{'venue': 'Inf. Process. Lett.', 'journal': 'Inf. Process. Lett.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}