Reports
A Note on Degree-Constrained Star Subgraphs of Bipartite Graphs ; CU-CS-083-75 Public Deposited
Downloadable Content
Download PDF
https://scholar.colorado.edu/concern/reports/bz60cx02x
- Abstract
- 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.
- Creator
- Date Issued
- 1975-10-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
aNoteOnDegreeConstrainedStarSubgraphsOfBipartiteGraphs.pdf | 2019-12-21 | Public | Download |