Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number (Q1092065): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q5615282 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5668915 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Cliques in random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4773670 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Couplages et transversaux généralises d'un hypergraphe infini / rank
 
Normal rank
Property / cites work
 
Property / cites work: A threshold for perfect matchings in random d-pure hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random hypergraph coloring algorithms and the weak chromatic number / rank
 
Normal rank
Property / cites work
 
Property / cites work: Component structure in the evolution of random hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotical Estimations for the Number of Cliques of Uniform Hypergraphs / rank
 
Normal rank

Latest revision as of 10:53, 18 June 2024

scientific article
Language Label Description Also known as
English
Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number
scientific article

    Statements

    Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number (English)
    0 references
    1987
    0 references
    The main results of this article are the representation of algorithms for several strong coloring problems (that are well-defined partitions of the set of vertices of a hypergraph in certain color sets) and the analysis of their performance in spaces of random hypergraphs. The so-called strong coloring algorithms \({\mathfrak KL}\gamma\) are fully described, they are proved in detail by using many theorems and lemmata and they exist of three phases which are analysed exactly. Furthermore it is shown that in these spaces the number of colors which are used by these algorithms is almost surely within a small constant factor (less than 4) of the strong chromatic number of the hypergraph. The article also contains a small summary of theorems concerning weak colorings and sparse hypergraphs and refers to some questions which are left open.
    0 references
    0 references
    0 references
    0 references
    0 references
    algorithms
    0 references
    coloring problems
    0 references
    random hypergraphs
    0 references
    strong coloring algorithms
    0 references
    strong chromatic number
    0 references
    weak colorings
    0 references
    sparse hypergraphs
    0 references