Vi beskriver en ny provtagningsbaserad metod för att bestämma snitt i en oriktad graf. För en graf (V, E), dess cykel utrymme är familjen av alla undergrupper av E som har jämn grad vid varje vertex. Vi bevisar att med stor sannolikhet, provtagning cykelutrymmet identifierar skärningarna i en graf. Detta leder till enkla nya linjär-tid sekventiella algoritmer för att hitta alla klippta kanter och klippa par (en uppsättning av 2 kanter som bildar ett snitt) av en graf. I modellen för distribuerad dator i en graf G = (V, E) med O(log  på V)-bit meddelanden, ger vårt tillvägagångssätt snabbare algoritmer för flera problem. Diametern på G betecknas med D, och den maximala graden av. Vi får enkla O(D)-tid distribuerade algoritmer för att hitta alla skärkanter, 2-kanten-anslutna komponenter, och klippa par, matcha eller förbättra vid tidigare tidsgränser. Under naturliga förhållanden dessa nya algoritmer är universellt optimala-det vill säga, en (D)-tid lägre gräns håller på varje graf. Vi får en O(D + / log  på V)-tid distribuerad algoritm för att hitta cut hörn; Detta är snabbare än den bästa tidigare algoritm när, D = O(  på V). En enkel förlängning av vårt arbete ger den första distribuerade algoritmen med sublinjär tid för 3-kantsanslutna komponenter. De grundläggande distribuerade algoritmerna är Monte Carlo, men de kan göras Las Vegas utan att öka den asymptotiska komplexiteten. I modellen för parallell databehandling på EREW PRAM ger vårt tillvägagångssätt en enkel algoritm med optimal tids komplexitet O(log V ) för att hitta kapade par och 3-kantsanslutna komponenter.
REF använder ett spännträd för att provsmaka cykelutrymmet för en graf på ett enhetligt sätt och på så sätt hitta små snitt (bestående av en enda kant, två kanter, eller en skär vertex) med hög sannolikhet.
Fast computation of small cuts via cycle space sampling
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}