Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Generowanie grafów z ograniczonym stopniem o danej liczbie chromatycznej
Języki publikacji
Abstrakty
The distribution of the chromatic number χ of random graphs with bounded degree (f-graphs) of order n generated in the G (n, f) model is studied. Introducing the predominant chromatic number results in determining values of parameters f and n that can be chosen in this model to generate graphs with a given χ.
Rozważa się zależność rozkładu prawdopodobieństwa liczby chromatycznej χ grafów losowych G (n, f) od parametrów modelu n (liczba wierzchołków) i f (ograniczenie stopnia). Grafy generowane w tym modelu są to maksymalne (krawędziowo) grafy z ograniczonym stopniem (f-grafy) odpowiadające stanom końcowym losowego procesu grafowego RfGP. W obszernym eksperymencie obliczeniowym wykorzystano algorytm generowania grafów G (n, f) i wprowadzając pojęcie dominującej liczby chromatycznej określono wartości f i n, przy których generowane są f-grafy o danej wartości χ.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
7--16
Opis fizyczny
Bibliogr. 7 poz., rys., tab.
Twórcy
autor
autor
autor
- Poznan University of Technology, pl. M. Sklodowskiej-Curie 5, 60-965 Poznan, Poland, balinska@man.poznan.pl
Bibliografia
- [1] Achlioptas D., Naor A., The Two Possible Values of the Chromatic Number of a Random Graph, Annals of Mathematics, 162 (2005), pp. 1335-1351.
- [2] Balińska K. T., Quintas L. V., Random Graphs with Bounded Degree, Publ. House , Poznań Univ. of Techn. Poznań (2006).
- [3] Balińska K. T., Quintas L. V., Zwierzyński K. T., The Chromatic Number of Edge Maximal Graphs with Bounded Degree, CSC Report No 545, Poznań Univ. of Techn., Poznań (2007), pp. 1-30.
- [4] Brooks R. L., On Colouring the Nodes of a Network , Proc. Cambridge Phios. Soc. 37 (1941), pp. 194-197.
- [5] Kennedy J. W., Quintas L. V., Probability Models for Random f-graphs, In: Combinatorial Mathematics (New York, 1985), Ann. N. Y. Acad. Sci., 555, (1989), pp. 248-261.
- [6] Sysło M. M., Deo N. Kowalik J. S., Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall (1983).
- [7] The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/squences/
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPC6-0001-0025