We show that computing (and even approximating) maximum clique and minimum graph coloring for circulant graphs is essentially as hard as in the general case. In contrast, we show that, under additional constraints, e.g., prime order and/or spareness, graph isomorphism and minimum graph coloring become easier in the circulant case, and we take advantage of spectral techniques for their efficient computation.

Hardness results and spectral techniques for combinatorial problems on circulant graphs / B. Codenotti, I. Gerace, S. Vigna. - In: LINEAR ALGEBRA AND ITS APPLICATIONS. - ISSN 0024-3795. - 285:1-3(1998), pp. 123-142.

Hardness results and spectral techniques for combinatorial problems on circulant graphs

S. Vigna
Ultimo
1998

Abstract

We show that computing (and even approximating) maximum clique and minimum graph coloring for circulant graphs is essentially as hard as in the general case. In contrast, we show that, under additional constraints, e.g., prime order and/or spareness, graph isomorphism and minimum graph coloring become easier in the circulant case, and we take advantage of spectral techniques for their efficient computation.
circulant matrices ; circulant graphs ; eigenvalues ; eigenvectors ; chromatic number ; clique ; approximation algorithms
Settore INF/01 - Informatica
1998
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/154168
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 37
social impact