Abstrakt. I detta dokument introducerar vi en ny enkel strategi i egg-searching av en graf, vilket är användbart för de olika subgraph listing problem. Genom att tillämpa strategin får vi följande fyra algoritmer. Den första listar alla trianglar i en graf G i O(a(G) Alla algoritmer kräver linjärt utrymme. Vi etablerar också en övre gräns på a(G) för en graf G: förekommer. I efterföljande avsnitt kommer vi att visa att proceduren ovan kräver O(a(G)m) tid. Genom hela detta papper m är antalet kanter av en graf G, n är antalet hörn av G, och a(G) är arboricity av G, det vill säga det minsta antalet kant-söndrade spännande skogar som G kan brytas ner [5]. Vi använder den ganska obekanta grafen invariant a(G) som parameter för att begränsa algoritmernas körtid. Strategin ger enkla algoritmer för problem att lista vissa typer av subgrafer i en graf. Typerna av dessa subgrafer inkluderar "triangel, fyrhörning", "fullständig subgraf av en fast ordning" och "clique". Våra algoritmer är lika snabba som de kända om någon, och en faktor n reduceras ofta till a(G) i tid komplexitet. I 2 ger vi en övre gräns på a(G) för en allmän graf G: a(G) <-
Chiba och Nishizeki REF ger gränser för en sekventiell version av MinBucket med hjälp av degeneracy av en graf.
Arboricity and subgraph listing algorithms
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}