opprobrious
发表于 2025-3-28 15:01:16
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.
专心
发表于 2025-3-28 20:33:02
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
发表于 2025-3-29 00:03:37
http://reply.papertrans.cn/39/3881/388044/388044_43.png
Assault
发表于 2025-3-29 05:03:35
http://reply.papertrans.cn/39/3881/388044/388044_44.png
Palpable
发表于 2025-3-29 07:32:16
http://reply.papertrans.cn/39/3881/388044/388044_45.png
tenosynovitis
发表于 2025-3-29 15:04:13
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
发表于 2025-3-29 16:25:40
http://reply.papertrans.cn/39/3881/388044/388044_47.png
娴熟
发表于 2025-3-29 20:55:50
http://reply.papertrans.cn/39/3881/388044/388044_48.png
软膏
发表于 2025-3-30 01:22:30
http://reply.papertrans.cn/39/3881/388044/388044_49.png
裤子
发表于 2025-3-30 06:39:42
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 ..