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.
Provtagning av cykelrum: Den teknik för provtagning av cykelrum som införts av Pritchard och Thurimella REF gör det möjligt att upptäcka små skärningar i en graf med hjälp av kopplingar mellan cyklerna och skärningar i en graf.
Fast computation of small cuts via cycle space sampling
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}