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. VignaUltimo
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.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.