Document Type

Technical Report

Publication Date

Fall 10-1-1975


Let f ne a positive-valued function on the vertices of a graph G. An f-star subgraph F consists of vertex-disjoint stars, where each vertex v meets at most f(v) edges of F; a maximum f-star subgraph contains the greatest number of edges possible. Let G be bipartite, with vertex sets S, T; let f(v) = 1 for all vɛS. Then there is a maximum f-star subgraph that contains a maximum matching. Let G have a perfect matching, let f(v)=1 for vɛS, f(v)≥2 for vɛT. Then an f-star subgraph covering all vertices of S can be found in 0(E log V) time. Also, a collection of vertex-disjoint paths of length 1 or 2 covering all vertives can be found in 0(E log V) time.