HARDNESS RESULTS AND SPECTRAL TECHNIQUES FOR COMBINATORIAL PROBLEMS ON CIRCULANT GRAPHS

Authors
CODENOTTI B GERACE I VIGNA S
Citation
B. Codenotti et al., HARDNESS RESULTS AND SPECTRAL TECHNIQUES FOR COMBINATORIAL PROBLEMS ON CIRCULANT GRAPHS, Linear algebra and its applications, 285(1-3), 1998, pp. 123-142
Citations number
16
Categorie Soggetti
Mathematics,Mathematics
Journal title
Linear algebra and its applications → ACNP
ISSN journal
00243795
Volume
285
Issue
1-3
Year of publication
1998
Pages
123 - 142
Database
ISI
SICI code
0024-3795(1998)285:1-3<123:HRASTF>2.0.ZU;2-O
Abstract
We show that computing (and even approximating) MAXIMUM CLIQUE and MIN IMUM GRAPH COLORING for circulant graphs is essentially as hard as in the general case. In contrast, we show that, under additional constrai nts, e.g., prime order and/or sparseness, GRAPH ISOMORPHISM and MINIMU M GRAPH COLORING become easier in the circulant case, and we take adva ntage of spectral techniques for their efficient computation. (C) 1998 Elsevier Science Inc. All rights reserved.