Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Kolmogorov random graphs only have trivial stable colorings
Autore:
Cheng, Q; Fang, F;
Indirizzi:
Univ So Calif, Dept Comp Sci, Los Angeles, CA 90089 USA Univ So Calif LosAngeles CA USA 90089 omp Sci, Los Angeles, CA 90089 USA Environm Syst Res Inst Inc, Redlands, CA 92373 USA Environm Syst Res Inst Inc Redlands CA USA 92373 , Redlands, CA 92373 USA
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 3, volume: 81, anno: 2002,
pagine: 133 - 136
SICI:
0020-0190(20020214)81:3<133:KRGOHT>2.0.ZU;2-7
Fonte:
ISI
Lingua:
ENG
Keywords:
combinatorial problems; regular graphs; graph automorphism; Kolmogorov complexity;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
7
Recensione:
Indirizzi per estratti:
Indirizzo: Cheng, Q Univ So Calif, Dept Comp Sci, Los Angeles, CA 90089 USA Univ So Calif Los Angeles CA USA 90089 Los Angeles, CA 90089 USA
Citazione:
Q. Cheng e F. Fang, "Kolmogorov random graphs only have trivial stable colorings", INF PROCESS, 81(3), 2002, pp. 133-136

Abstract

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundations of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective version of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a byproduct, we also give an upper bound of the size of induced regular subgraphsin random graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 18/01/20 alle ore 21:38:15