Titlebook: ;

opprobrious

Near-optimal dominating sets in dense random graphs in polynomial expected time,The existence and efficient finding of small dominating sets in dense random graphs is examined in this work. We show, for the model .. with .=1/2, that:.Our results extend to the case G. with . fixed to any constant < 1.

专心

A rainbow about ,-colorings for complete graphs,Given a finite set . of positive integers, with 0 ε ., a .-coloring of a graph . is a function . → IN. such that for each . ∉ .. The .-span is the difference between the largest and smallest color and the .-span of . is the minimum span over all .-colorings of .. We show that the problem to find the .-span for a complete graph is NP-complete.

Admonish

Assault

Palpable

tenosynovitis

Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequalinear performance ratio. As was the case in the development of sequential complexity theory, matching problems are on the boundary of what problems might ultimately be described as . for parallel computation. Future work in this area is likely to decide whether these ought to be regarded as those problems in . or those problems in ..

troponins

娴熟

软膏

裤子

Dynamic algorithms for graphs with treewidth 2, can be performed in .(log .) time. For a large number of graph decision, optimization and counting problems, information can be maintained using .(log .) time per update, such that queries can be resolved in .(log .) or .(1) time. Similar results hold for the classes of almost trees with parameter ., for fixed ..