Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

DOI10.1134/S0032946011030057zbMath1236.05063MaRDI QIDQ764406

T. A. Urbanovich, Maxim A. Babenko

Publication date: 13 March 2012

Published in: Problems of Information Transmission (Search for Journal in Brave)

zbMATH Keywords

almost \(d\)-regular graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Cites Work

• Regular subgraphs of almost regular graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Perfect Matching for Biconnected Cubic Graphs in O(n log2 n) Time
• Unnamed Item

This page was built for publication: Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph