Abstract Algorithms of O(p. n. log n) time to find an (absolute or vertex) p‐center on a weighted tree of n vertices are presented. Those algorithms represent improvement over previous known results in the range p < log n (for the vertex p‐center problem) and in the range p < log n. log log n (for the absolute p‐center problem).

A minimum edge coloring of a bipartite graph is a partition of the edges into $\Delta $ matchings, where $\Delta $ is the maximum degree in the graph. Coloring algorithms that run in time $O(\min (m(\log n)^2 ,n^2 \log n))$ are presented. The algorithms rely on an efficient procedure for the special case of $\Delta $ an exact power of two. The coloring algorithms can be used to find maximum cardinality matchings on regular bipartite graphs in the above time bound. An algorithm for coloring multigraphs with large multiplicities is also presented.

A minimum edge coloring of a bipartite graph is a partition of the edges into Δ matchings, where Δ is the maximum degree in the graph. Coloring algorithms are presented that use time O(min(¦E¦ Δ log n, ¦E¦ @@@@n log n, n2log Δ)) and space O(nΔ). This compares favorably to the previous O(¦E¦ [equation] log Δ) time bound. The coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. The time bounds compare favorably to the O(¦E¦ @@@@n) matching algorithm, expect when [equation] ≤ Δ ≤ @@@@n log n.

This work presents a new efficient algorithm for finding a maximum matching in an arbitrary graph. Two implementations are suggested, the complexity of the first is O(n2.5) and the complexity of the second is O(m√n·log n) where n, m are the numbers of the vertices and the edges in the graph.