Vi presenterar ett sortiment av metoder för att hitta och räkna enkla cykler av en given längd i riktade och oriktade grafer. De flesta av de gränser som erhålls beror enbart på antalet kanter i diagrammet i fråga, och inte på antalet hörn. De gränser som erhållits förbättras på olika tidigare kända resultat. Nyckelord. Grafiska algoritmer, cykler. 1. Vad är det för fel på dig? Inledning. Problemet med att bestämma huruvida en givengraphG = (V, E) innehåller en enkel cykel av längd k är bland de mest naturliga och lätt angivna algoritmiska grafproblem. Om cykeln längd k är en del av inmatningen, då problemet är helt klart NPfullständig som det inkluderar i synnerhet Hamiltonian cykel problem. För varje fast k, men problemet kan lösas i antingen O(VE) tid [11] där w < 2.376 är exponenten för matris multiplikation. Det viktigaste bidraget av detta papper är en samling nya gränser på komplexiteten av att hitta enkla cykler av längd exakt k, där k > 3 är ett fast heltal, i en riktad eller en oriktad graf G = (V, E). Dessa gränser är av formen O (E ~k ) eller av formen O(E ~k.d(G)• där d(G) är degeneracy av grafen (se nedan). Gränserna förbättras vid tidigare kända gränser när grafen i fråga är relativt gles eller relativt degenererad. Vi lät Ck stå för en enkel cykel av längd k. När man överväger riktade grafer, en Ck antas vara riktad. Vi visar att en Ck i en riktad eller oriktad graf G = (V, E), om en finns, kan hittas i O(E 2-2/k) tid, om k är jämn, och i O(E 2-2/(k+1) tid, om k är udda. För att hitta trianglar (C3's), får vi den något bättre bundet av O(E 2~176 = O(EI41), där w < 2.376 är exponenten för matris multiplikation. Även cykler i oriktade grafer kan hittas ännu snabbare. En C4k-2 i en oriktad graf G = (V, E), om en finns, kan hittas i O(E 2-(l/2k)tl+l/k) tid. En Cak, om en finns, kan hittas i O(E 2-(l/k-t/(2k+~))) tid. I synnerhet kan vi hitta en oriktad Ca i O(E 4/3) tid och en oriktad C6 i O(E 13/8) tid. Degeneracy d(G) i en oriktad graf G---(V, E) är det minsta antal d för vilket det finns en acyklisk orientering av G där alla utgrader är som mest d. Degeneracy d(G) i en graf G är linjärt relaterad till arboricity a(G) i grafen, dvs a(G) = (-) (d(G)), där a(G) är det minsta antal skogar som behövs I
Alon, Yuster och Zwick REF visade hur man detekterar en triangel i tiden O(e 2 och/eller +1).
Finding and counting given length cycles
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}