E-viri
Recenzirano
Odprti dostop
-
Kluge, Laurence
Computational complexity, 12/2024, Letnik: 33, Številka: 2Journal Article
The combinatorial refinement techniques have proven to be an efficient approach to isomorphism testing for particular classes of graphs. If the number of refinement rounds is small, this puts the corresponding isomorphism problem in a low-complexity class. We investigate the round complexity of the two-dimensional Weisfeiler--Leman algorithm on circulant graphs, i.e., on Cayley graphs of the cyclic group Z n , and prove that the number of rounds until stabilization is bounded by O ( d ( n ) log n ) , where d ( n ) is the number of divisors of n. As a particular consequence, isomorphism can be tested in NC for connected circulant graphs of order p ℓ with p an odd prime, ℓ > 3 and vertex degree Δ smaller than p. We also show that the color refinement method (also known as the one-dimensional Weisfeiler--Leman algorithm) computes a canonical labeling for every non-trivial circulant graph with a prime number of vertices after individualization of two appropriately chosen vertices. Thus, the canonical labeling problem for this class of graphs has at most the same complexity as color refinement, which results in a time bound of O ( Δ n log n ) . Moreover, this provides a first example where a sophisticated approach to isomorphism testing put forward by Tinhofer has a real practical meaning.
Avtor
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.