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.
Pubblicazioni consigliate
I metadati presenti in AIR sono rilasciati con licenza CCO mentre i file delle pubblicazioni sono rilasciati con licenza CC BY-SA, salvo diversa indicazione. In caso di violazione di copyright, contattare l'assistenza di AIR
