Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Deciding k-colorability in expected polynomial time
Autore:
Krivelevich, M;
Indirizzi:
Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel Tel Aviv Univ Tel Aviv Israel IL-69978 t Math, IL-69978 Tel Aviv, Israel
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 1, volume: 81, anno: 2002,
pagine: 1 - 6
SICI:
0020-0190(20020116)81:1<1:DKIEPT>2.0.ZU;2-T
Fonte:
ISI
Lingua:
ENG
Soggetto:
GRAPH-COLORING PROBLEM; CHROMATIC NUMBER; INDEPENDENCE NUMBER;
Keywords:
algorithms; graph coloring; average complexity; vector chromatic number;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
15
Recensione:
Indirizzi per estratti:
Indirizzo: Krivelevich, M Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel Tel Aviv Univ Tel Aviv Israel IL-69978 8 Tel Aviv, Israel
Citazione:
M. Krivelevich, "Deciding k-colorability in expected polynomial time", INF PROCESS, 81(1), 2002, pp. 1-6

Abstract

For every fixed k greater than or equal to 3 we describe an algorithm for deciding k-colorability, whose expected running time in polynomial in the probability space G(n, p) of random graphs as long as the edge probability p= p(n) satisfies p(n) greater than or equal to C/n, with C = C(k) being a sufficiently large constant. (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 25/01/20 alle ore 16:04:35