Tyck till om SwePub Sök
här!
Sökning: id:"swepub:oai:lup.lub.lu.se:565c876a-63c8-4e92-ac46-06177cd8d6e0" >
Finding Small Compl...
Finding Small Complete Subgraphs Efficiently
-
- Dumitrescu, Adrian (författare)
- Algoresearch L.L.C.
-
- Lingas, Andrzej (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Hsieh, Sun-Yuan (redaktör/utgivare)
-
visa fler...
-
Hung, Ling-Ju (redaktör/utgivare)
-
Lee, Chia-Wei (redaktör/utgivare)
-
visa färre...
-
Algoresearch LL.C. Institutionen för datavetenskap (creator_code:org_t)
- 2023
- 2023
- Engelska 12 s.
-
Ingår i: Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Proceedings. - 0302-9743 .- 1611-3349. - 9783031343469 ; 13889 LNCS, s. 185-196
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- (I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m3 / 2) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on m and α in the running time O(αℓ-2· m) of the algorithm of Chiba and Nishizeki for listing all copies of Kℓ, where ℓ≥ 3, is asymptotically tight. (III) We give improved arboricity-sensitive running times for counting and/or detection of copies of Kℓ, for small ℓ≥ 4. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every ℓ≥ 7.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- graph arboricity
- rectangular matrix multiplication
- subgraph detection/counting
- triangle
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas