Isomorphism testing for circulant graphs Cn(a,b) (Altre pubblicazioni)

Type
Label
  • Isomorphism testing for circulant graphs Cn(a,b) (Altre pubblicazioni) (literal)
Anno
  • 2010-01-01T00:00:00+01:00 (literal)
Alternative label
  • NICOLOSO Sara; PIETROPAOLI Ugo (2010)
    Isomorphism testing for circulant graphs Cn(a,b)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • NICOLOSO Sara; PIETROPAOLI Ugo (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni
  • Pubblicato sulla rivista elettronica Optimization Online, il 22 Marzo 2010 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://www.optimization-online.org/DB_FILE/2010/03/2577.pdf (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • NICOLOSO Sara, IASI-CNR; PIETROPAOLI Ugo, Università di Roma Tor Vergata (literal)
Titolo
  • Isomorphism testing for circulant graphs Cn(a,b) (literal)
Abstract
  • In this paper we focus on connected directed/undirected circulant graphs Cn(a,b). We investigate some topological characteristics, and define a simple combinatorial model, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test whether two circulant graphs Cn(a, b) and Cn(a',b') are isomorphic or not. The method is entirely elementary and consists of comparing two suitably computed integers in {1, . . . , n / (gcd(n,a) gcd(n,b)) - 1}, and of verifying if {gcd(n, a), gcd(n, b)} = {gcd(n, a' ), gcd(n, b' )}. It also allows for building the mapping function in linear time. In addition, properties of the classes of mutually isomorphic graphs are analyzed. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Insieme di parole chiave di
data.CNR.it