Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph
Maxim A. Babenko, T. A. Urbanovich · Problems of Information Transmission · 2011
We consider almost d-regular graphs, i.e., graphs having all vertex degrees equal to either d or d − 1. It is known that for each d′ ≤ d every d-regular graph contains an almost d′-regular spanning subgraph. We give an algorithm for selecting such a subgraph in optimal linear time.