Att lista alla enkla cykler (nedan kallade cykler) i en graf är ett klassiskt problem vars effektiva lösningar går tillbaka till början av 70-talet. För en graf med n hörn och m kanter, som innehåller η cykler, den mest kända lösningen i litteraturen ges av Johnsons algoritm [SIAM J. Computing, 1975] och tar O((η + 1)(m + n) tid. Denna lösning är förvånansvärt inte optimal för oriktade grafer: så vitt vi vet har inga teoretiskt snabbare lösningar föreslagits på nästan 40 år. Vi presenterar den första optimala lösningen för att lista alla cykler i en oriktad graf G, förbättra tidsbunden av Johnsons algoritm med en faktor som kan vara O(n 2 ). Specifikt, låt C(G) betecknar uppsättningen av alla dessa cykler, och observera att  och C(G) = η. För en cykel c  och C (G), låt  och c) betecknar antalet kanter i c. Vår algoritm kräver O(m + c till C (G)  och är asymptotiskt optimal: faktiskt,  på (m) tid krävs nödvändigtvis för att läsa G som ingång, och  på C till C (G) c) tid krävs nödvändigtvis för att lista utdata. Vi beskriver sedan en oändlig familj av täta grafer, där varje graf med n hörn och m kanter innehåller η =  och (m) cykler c med C = O(1) kanter. För varje graf i denna familj, kräver vår algoritm 2 ) tid jämfört med Johnsons algoritm. I allmänhet för alla grafer, eftersom  och c ≤ n, kostnaden för vår algoritm aldrig överstiger O(m + (η + 1)n) tid. Vi presenterar också den första optimala lösningen för att lista alla enkla stigar från s till t (kort, st-sökvägar) i en oriktad graf G. Låt P st (G) beteckna uppsättningen av st-sökvägar i G och, för en st-sökväg π  och P st (G), låt  till exempel vara antalet kanter i π. Vår algoritm listar alla st-patter i G optimalt i O(m + π och Pst(G)  och observerar att tid är nödvändig för att lista utdata. Medan den grundläggande metoden är enkel (se binär partition i punkt 3), använder vi ett antal icke-triviala idéer för att få vår optimala algoritm för en oriktad (ansluten) graf G som begreppsmässigt listas nedan. 1. Vad är det för fel på dig? Bevisa följande minskning. Om det finns en optimal algoritm för att lista st-vägarna i G, finns det en optimal algoritm för att lista cyklerna i G. Detta relaterar C(G) och P st (G) för vissa val s, t. 2. Fokusera på att lista st-vägarna. Betrakta sönderdelningen av grafen i bianslutna komponenter (bccs), så bildar ett träd T där två bccs är intilliggande i T iff de delar en artikulation punkt. Utnyttja (och bevisa) egenskapen att om s och t tillhör distinkta bccs, då (i) det finns en unik sekvens B s,t av intilliggande bccs i T genom vilka varje st-path måste passera, och (ii) varje st-path är konkatetering av stigar som förbinder artikulationspunkterna av dessa bccs i B s,t. 3. Vad är det som händer? Listar regelbundet st-patterna i B s,t med hjälp av den klassiska binära partitionen (dvs. med en kant e i G, lista alla cykler som innehåller e, och sedan alla cykler som inte innehåller e): nu räcker det att arbeta på den första bcc i B s,t, och effektivt underhålla den när du tar bort en kant e, som krävs av den binära partitionen. 4. Vad är det som händer? Använd en definition av certifikat för att undvika rekursiva samtal (i den binära partitionen) som inte listar nya st-sökvägar. Detta certifikat upprätthålls dynamiskt som en datastruktur som representerar den första bcc i B s,t, som garanterar att det finns minst en ny lösning i den nuvarande B s,t. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Tänk på det binära rekursionsträdet som motsvarar den binära partitionen. Dela upp detta träd i ryggrader: en ryggrad motsvarar rekursiva samtal som genereras av kanterna e tillhör samma adjacency lista i B s,t. Den amorterade kostnaden för varje listad st-path π är O( och) om det finns en garanti för att den amorterade kostnaden i varje ryggrad S är O(μ), där μ är en lägre gräns på antalet st-patter som kommer att listas från rekursiva samtal som tillhör S. Den (okända) parameter μ olika för varje ryggrad S, och motsvarande kostnad O(μ), kommer att driva utformningen av de föreslagna algoritmerna.
För oriktade grafer presenterade Ferreira et.al REF nyligen en mer optimal algoritm.
Optimal Listing of Cycles and st-Paths in Undirected Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}